Алгоритмы поиска с возвратом для построения гамильтонова разложения 4-регулярного мультиграфа

Рассматривается задача построения гамильтонова разложения регулярного мультиграфа на гамильтоновы циклы без общих рёбер. Известно, что проверка несмежности вершин в полиэдральных графах симметричного и асимметричного многогранников коммивояжёра является NP-полной задачей. С другой стороны, достаточное условие несмежности вершин можно сформулировать в виде комбинаторной задачи построения гамильтонова разложения 4-регулярного мультиграфа. В статье представлены два алгоритма поиска с возвратом для проверки несмежности вершин в полиэдральном графе коммивояжёра и построения гамильтонова разложения 4-регулярного мультиграфа: алгоритм на основе последовательного расширения простого пути и алгоритм на основе процедуры цепного фиксирования рёбер. По результатам вычислительных экспериментов для неориентированных мультиграфов оба переборных алгоритма проиграли известному эвристическому алгоритму поиска с переменными окрестностями. Однако для ориентированных мультиграфов алгоритм на основе цепного фиксирования рёбер показал сопоставимые результаты с эвристиками на экземплярах задачи, имеющих решение, и лучшие результаты на экземплярах задачи, для которых гамильтонова разложения не существует.

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.