Geodesic
Backtracking algorithms for constructing the Hamiltonian decomposition of a $4$-regular multigraph
Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 1, pp. 6-21.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the $1$-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a $4$-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the $1$-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist.
Keywords: Hamiltonian decomposition, traveling salesperson polytope, $1$-skeleton, vertex adjacency, backtracking. 
@article{MAIS_2021_28_1_a0,
     author = {A. V. Korostil and A. V. Nikolaev},
     title = {Backtracking algorithms for constructing the {Hamiltonian} decomposition of a $4$-regular multigraph},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {6--21},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a0/}
}
TY  - JOUR
AU  - A. V. Korostil
AU  - A. V. Nikolaev
TI  - Backtracking algorithms for constructing the Hamiltonian decomposition of a $4$-regular multigraph
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2021
SP  - 6
EP  - 21
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a0/
LA  - ru
ID  - MAIS_2021_28_1_a0
ER  - 
%0 Journal Article
%A A. V. Korostil
%A A. V. Nikolaev
%T Backtracking algorithms for constructing the Hamiltonian decomposition of a $4$-regular multigraph
%J Modelirovanie i analiz informacionnyh sistem
%D 2021
%P 6-21
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a0/
%G ru
%F MAIS_2021_28_1_a0
A. V. Korostil; A. V. Nikolaev. Backtracking algorithms for constructing the Hamiltonian decomposition of a $4$-regular multigraph. Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 1, pp. 6-21. http://geodesic.mathdoc.fr/item/MAIS_2021_28_1_a0/

[1] J. Krarup, “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, NATO Advanced Study Institutes Series, 19, Springer Netherlands, 1995, 173–178 | DOI | MR

[2] M. M. Bae, B. Bose, “Edge disjoint hamiltonian cycles in $k$-ary $n$-cubes and hypercubes”, IEEE Transactions on Computers, 52:10 (2003), 1271–1284 | DOI

[3] R. F. Bailey, “Error-correcting codes from permutation groups”, Discrete Mathematics, 309:13 (2009), 4253–4265 | DOI | MR | Zbl

[4] C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, M. Y. Zhu, “Tools for privacy preserving distributed data mining”, SIGKDD Explor. Newsl., 4:2 (2002), 28–34 | DOI

[5] R. W. Hung, “Embedding two edge-disjoint hamiltonian cycles into locally twisted cubes”, Theoretical Computer Science, 412:35 (2011), 4747–4753 | DOI | MR | Zbl

[6] R. Glebov, Z. Luria, B. Sudakov, “The number of hamiltonian decompositions of regular graphs”, Israel Journal of Mathematics, 222:1 (2017), 91–108 | DOI | MR | Zbl

[7] G. Dantzig, R. Fulkerson, S. Johnson, “Solution of a large-scale traveling-salesman problem”, Journal of the Operations Research Society of America, 2:4 (1954), 393–410 | DOI | MR | Zbl

[8] D. L. Applegate, R. E. Bixby, V. Chvatál, W. J. Cook, The traveling salesman problem: a computational study, Princeton University Press, 2006 | MR | Zbl

[9] N. E. Aguilera, R. D. Katz, P. B. Tolomei, “Vertex adjacencies in the set covering polyhedron”, Discrete Applied Mathematics, 218 (2017), 40–56 | DOI | MR | Zbl

[10] M. L. Balinski, “Signature methods for the assignment problem”, Operations Research, 33:3 (1985), 527–536 | DOI | MR | Zbl

[11] C. R. Chegireddy, H. W. Hamacher, “Algorithms for finding $k$-best perfect matchings”, Discrete Applied Mathematics, 18:2 (1987), 155–165 | DOI | MR | Zbl

[12] E. F. Combarro, P. Miranda, “Adjacency on the order polytope with applications to the theory of fuzzy measures”, Fuzzy Sets and Systems, 161:5 (2010), 619–641 | DOI | MR | Zbl

[13] H. N. Gabow, “Two algorithms for generating weighted spanning trees in order”, SIAM Journal on Computing, 6:1 (1977), 139–150 | DOI | MR | Zbl

[14] V. A. Bondarenko, “Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms”, Automation and Remote Control, 44:9 (1983), 1137–1142 | MR | Zbl

[15] V. Bondarenko, A. Nikolaev, “On graphs of the cone decompositions for the min-cut and max-cut problems”, International Journal of Mathematics and Mathematical Sciences, 2016 (2016), 7863650 | DOI | MR | Zbl

[16] M. Grötschel, M. Padberg, “Polyhedral theory”, The traveling salesman problem: a guided tour of combinatorial optimization, John Wiley, Chichester, 1985, 251–305 | MR

[17] C. H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is np-complete”, Mathematical Programming, 14:1 (1978), 312–324 | DOI | MR | Zbl

[18] V. A. Bondarenko, A. V. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, Journal of Applied and Industrial Mathematics, 12:1 (2018), 9–18 | DOI | MR | Zbl

[19] A. Nikolaev, “On vertex adjacencies in the polytope of pyramidal tours with step-backs”, Mathematical optimization theory and operations research, Motor 2019, LNCS, 11548, Springer, 2019, 247–263 | DOI | Zbl

[20] T. S. Arthanari, “On pedigree polytopes and hamiltonian cycles”, Discrete Mathematics, 306:14 (2006), 1474–1492 | DOI | MR | Zbl

[21] T. S. Arthanari, “Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope”, Discrete Optimization, 10:3 (2013), 224–232 | DOI | MR | Zbl

[22] M. R. Rao, “Adjacency of the traveling salesman tours and $0 - 1$ vertices”, SIAM Journal on Applied Mathematics, 30:2 (1976), 191–198 | DOI | MR | Zbl

[23] B. Péroche, “Np-completeness of some problems of partitioning and covering in graphs”, Discrete Applied Mathematics, 8:2 (1984), 195–208 | DOI | MR | Zbl

[24] A. Kozlova, A. Nikolaev, “Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope”, Mathematical optimization theory and operations research, Motor 2019, LNCS, 11548, Springer, 2019, 374–389 | DOI | Zbl

[25] A. Nikolaev, A. Kozlova, “Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search”, Journal of Combinatorial Optimization, 2020 | DOI | MR

[26] S. S. Skiena, The algorithm design manual, Springer, 2008 | DOI | MR | Zbl

[27] A. V. Korostil, A. V. Nikolaev, “backtracking algorithm to construct the hamiltonian decomposition of a 4-regular multigraph”, Notes on Computer Science and Mathematics, 12, P.G. Demidov Yaroslavl State University, 2020, 91–97 | MR

[28] D. E. Knuth, The art of computer programming, v. 2, Seminumerical algorithms, 3rd ed., Addison-Wesley Longman Publishing Co., Inc., USA, 1997 | DOI | MR

[29] J. H. Kim, N. C. Wormald, “Random matchings which induce hamilton cycles and hamiltonian decompositions of random regular graphs”, Journal of Combinatorial Theory, Series B, 81:1 (2001), 20–44 | DOI | MR | Zbl