Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
https://doi.org/10.18255/1818-1015-2021-1-6-21
Abstract
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
MSC2020: 05C85, 52B05
Supporting agencies: This work was supported by P. G. Demidov Yaroslavl State University Project № VIP-016
About the Authors
Alexander V. Korostil
P. G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
Postgraduate student
14 Sovetskaya, Yaroslavl 150003
Andrei V. Nikolaev
P. G. Demidov Yaroslavl State University
Russian Federation
Russian Federation
PhD, associate professor
14 Sovetskaya, Yaroslavl 150003
References
1. J. Krarup, The peripatetic salesman and some related unsolved problems”, in Combinatorial Programming: Methods and Applications, vol. 19, Springer Netherlands, 1995, pp. 173–178. doi: 10.1007/978-94-011-7557-9_8.
2. M. M. Bae and B. Bose, “Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes”, IEEE Transactions on Computers, vol. 52, no. 10, pp. 1271–1284, 2003. doi: 10.1109/TC.2003.1234525.
3. R. F. Bailey, “Error-correcting codes from permutation groups”, Discrete Mathematics, vol. 309, no. 13, pp. 4253–4265, 2009. doi: 10.1016/j.disc.2008.12.027.
4. C. Clifton, M. Kantarcioglu, J. Vaidya, X. Lin, and M. Y. Zhu, “Tools for Privacy Preserving Distributed Data Mining”, SIGKDD Explor. Newsl., vol. 4, no. 2, pp. 28–34, 2002. doi: 10.1145/772862.772867.
5. R. W. Hung, “Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes”, Theoretical Computer Science, vol. 412, no. 35, pp. 4747–4753, 2011. doi: 10.1016/j.tcs.2011.05.004.
6. R. Glebov, Z. Luria, and B. Sudakov, “The number of Hamiltonian decompositions of regular graphs”, Israel Journal of Mathematics, vol. 222, no. 1, pp. 91–108, 2017. doi: 10.1007/s11856-017-1583-y.
7. G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem”, Journal of the Operations Research Society of America, vol. 2, no. 4, pp. 393–410, 1954. doi: 10.1287/opre.2.4.393.
8. D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, ´ The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006, isbn: 9780691129938.
9. N. E. Aguilera, R. D. Katz, and P. B. Tolomei, “Vertex adjacencies in the set covering polyhedron”, Discrete Applied Mathematics, vol. 218, pp. 40–56, 2017. doi: 10.1016/j.dam.2016.10.024.
10. M. L. Balinski, “Signature Methods for the Assignment Problem”, Operations Research, vol. 33, no. 3, pp. 527–536, 1985. doi: 10.1287/opre.33.3.527.
11. C. R. Chegireddy and H. W. Hamacher, “Algorithms for finding K-best perfect matchings”, Discrete Applied Mathematics, vol. 18, no. 2, pp. 155–165, 1987. doi: 10.1016/0166-218X(87)90017-5.
12. E. F. Combarro and P. Miranda, “Adjacency on the order polytope with applications to the theory of fuzzy measures”, Fuzzy Sets and Systems, vol. 161, no. 5, pp. 619–641, 2010. doi: 10.1016/j.fss.2009.05.004.
13. H. N. Gabow, “Two Algorithms for Generating Weighted Spanning Trees in Order”, SIAM Journal on Computing, vol. 6, no. 1, pp. 139–150, 1977. doi: 10.1137/0206011.
14. V. A. Bondarenko, “Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms”, Automation and Remote Control, vol. 44, no. 9, pp. 1137–1142, 1983.
15. V. Bondarenko and A. Nikolaev, “On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems”, International Journal of Mathematics and Mathematical Sciences, vol. 2016, p. 7 863 650, 2016. doi: 10.1155/2016/7863650.
16. M. Grotschel and M. Padberg, “Polyhedral theory”, in ¨ The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley, Chichester, 1985, pp. 251–305.
17. C. H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is NP-Complete”, Mathematical Programming, vol. 14, no. 1, pp. 312–324, 1978. doi: 10.1007/BF01588973.
18. V. A. Bondarenko and A. V. Nikolaev, “On the Skeleton of the Polytope of Pyramidal Tours”, Journal of Applied and Industrial Mathematics, vol. 12, no. 1, pp. 9–18, 2018. doi: 10.1134/S1990478918010027.
19. A. Nikolaev, “On vertex adjacencies in the polytope of pyramidal tours with step-backs”, in Mathematical Optimization Theory and Operations Research. MOTOR 2019, ser. LNCS, vol. 11548, Springer, 2019, pp. 247–263. doi: 10.1007/978-3-030-22629-9_18.
20. T. S. Arthanari, “On pedigree polytopes and Hamiltonian cycles”, Discrete Mathematics, vol. 306, no. 14, pp. 1474–1492, 2006. doi: 10.1016/j.disc.2005.11.030.
21. T. S. Arthanari, “Study of the pedigree polytope and a suffciency condition for nonadjacency in the tour polytope”, Discrete Optimization, vol. 10, no. 3, pp. 224–232, 2013. doi: 10.1016/j.disopt.2013.07.001.
22. M. R. Rao, “Adjacency of the Traveling Salesman Tours and 0 − 1 Vertices”, SIAM Journal on Applied Mathematics, vol. 30, no. 2, pp. 191–198, 1976. doi: 10.1137/0130021.
23. B. Peroche, “NP-completeness of some problems of partitioning and covering in graphs”, ´ Discrete Applied Mathematics, vol. 8, no. 2, pp. 195–208, 1984. doi: 10.1016/0166-218X(84)90101-X.
24. A. Kozlova and A. Nikolaev, “Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope”, in Mathematical Optimization Theory and Operations Research. MOTOR 2019, ser. LNCS, vol. 11548, Springer, 2019, pp. 374–389. doi: 10.1007/978-3-030-22629-9_26.
25. A. Nikolaev and 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: 10.1007/s10878-020-00652-7.
26. S. S. Skiena, The Algorithm Design Manual. Springer, 2008. doi: 10.1007/978-1-84800-070-4.
27. A. V. Korostil and A. V. Nikolaev, “Algoritm poiska s vozvratom dlya postroeniya gamil’tonova razlozheniya 4-regulyarnogo mul’tigrafa (Backtracking algorithm to construct the Hamiltonian decomposition of a 4-regular multigraph)”, in Zametki po informatike i matematike (Notes on Computer Science and Mathematics), vol. 12, P.G. Demidov Yaroslavl State University, 2020, pp. 91–97.
28. D. E. Knuth, The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. USA: Addison-Wesley Longman Publishing Co., Inc., 1997, isbn: 0201896842. doi: 10.5555/270146.
29. J. H. Kim and N. C. Wormald, “Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs”, Journal of Combinatorial Theory, Series B, vol. 81, no. 1, pp. 20–44, 2001. doi: 10.1006/jctb.2000.1991.
Review
For citations:
Korostil A.V., Nikolaev A.V. Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph. Modeling and Analysis of Information Systems. 2021;28(1):6-21. (In Russ.) https://doi.org/10.18255/1818-1015-2021-1-6-21
Views:
732
Email this article 