maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2021-1-6-21mais-1469Research ArticleAlgorithmsАлгоритмы поиска с возвратом для построения гамильтонова разложения 4-регулярного мультиграфаBacktracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraphhttps://orcid.org/0000-0003-1881-0207КоростильАлександр ВасильевичKorostilAlexander V.

Аспирант

ул. Советская, 14, г. Ярославль, 150003

Postgraduate student

14 Sovetskaya, Yaroslavl 150003

av.korostil@gmail.comhttps://orcid.org/0000-0003-4705-2409НиколаевАндрей ВалерьевичNikolaevAndrei V.

Кандидат физико-математических наук, доцент

ул. Советская, 14, г. Ярославль, 150003

PhD, associate professor

14 Sovetskaya, Yaroslavl 150003

andrei.v.nikolaev@gmail.comЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202122032021281621Copyright © Коростиль А.В., Николаев А.В., 20212021Коростиль А.В., Николаев А.В.Korostil A.V., Nikolaev A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1469

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

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.

Гамильтоново разложениемногогранник коммивояжёраполиэдральный графсмежность вершинпоиск с возвратомHamiltonian decompositiontraveling salesperson polytope1-skeletonvertex adjacencybacktrackingРабота выполнена в рамках инициативной НИР ЯрГУ им. П. Г. Демидова № VIP-016This work was supported by P. G. Demidov Yaroslavl State University Project № VIP-016ReferencesJ. 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.S. S. Skiena, The Algorithm Design Manual. Springer, 2008. doi: 10.1007/978-1-84800-070-4.S. S. Skiena, The Algorithm Design Manual. Springer, 2008. doi: 10.1007/978-1-84800-070-4.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.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.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.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.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.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.

The authors declare that there are no conflicts of interest present.