Некоторые полиномиальные подклассы задачи об эйлеровом маршруте в кратном графе

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Рассматривается задача об эйлеровом маршруте (цикле или цепи) в кратном графе, которая обобщает классическую задачу для обычного графа. Задача о кратном эйлеровом маршруте является NP-трудной. Обоснована полиномиальность двух подклассов задачи о кратном эйлеровом маршруте, разработаны полиномиальные алгоритмы. В первом подклассе задано ограничение на множества достижимости по обычным ребрам, которые представляют собой подмножества вершин, соединенных только обычными ребрами. Во втором подклассе задано ограничение на степень квазивершин в графе с квазивершинами. Структура этого обычного графа отражает структуру кратного графа, а каждая квазивершина определяется $k$ индексами множеств достижимости по обычным ребрам, которые инцидентны какому-то мультиребру.

1. A. V. Smirnov, “The Shortest Path Problem for a Multiple Graph,” Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 625–633, 2018, doi: 10.3103/S0146411618070234.

2. V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks,” Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60–68, 2011.

3. A. V. Smirnov, “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases,” Automatic Control and Computer Sciences, vol. 50, no. 7, pp. 527–535, 2016, doi: 10.3103/S0146411616070191.

4. L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.

5. V. S. Roublev and A. V. Smirnov, “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution,” Modeling and Analysis of Information Systems, vol. 17, no. 2, pp. 72–98, 2010.

6. A. V. Smirnov, “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix,” Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 558–566, 2017, doi: 10.3103/S0146411617070185.

7. A. V. Smirnov, “The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph,” Modeling and Analysis of Information Systems, vol. 30, no. 3, pp. 264–282, 2023, doi: 10.18255/1818-1015-2023-3-264-282.

8. C. Hierholzer, “Über die M‘oglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren,” Mathematische Annalen, vol. 6, no. 1, pp. 30–32, 1873, doi: 10.1007/BF01442866.

9. C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.

10. Z. Lonc and P. Naroski, “On Tours that contain all Edges of a Hypergraph,” The Electronic Journal of Combinatorics, vol. 17, p. R144, 2010, doi: 10.37236/416.

11. A. Marino and A. Silva, “Eulerian Walks in Temporal Graphs,” Algoritmica, vol. 85, no. 3, pp. 805–830, 2023, doi: 10.1007/s00453-022-01021-y.

12. S. W. Bent and U. Manber, “On non-intersecting Eulerian circuits,” Discrete Applied Mathematics, vol. 18, no. 1, pp. 87–94, 1987, doi: 10.1016/0166-218X(87)90045-X.

13. S. Jimbo, “The NP-completeness of Eulerian Recurrent Length for 4-regular Eulerian Graphs,” in Proceedings of the 2014 4th International Conference on Artificial Intelligence with Applications in Engineering and Technology, 2014, pp. 155–159, doi: 10.1109/ICAIET.2014.34.

14. A. V. Smirnov, “NP-completeness of the Eulerian walk problem for a multiple graph,” Modeling and Analysis of Information Systems, vol. 31, no. 1, pp. 102–114, 2024, doi: 10.18255/1818-1015-2024-1-102-114.

15. J. Abrham and A. Kotzig, “Transformations of Euler Tours,” Annals of Discrete Mathematics, vol. 8, pp. 65–69, 1980, doi: 10.1016/S0167-5060(08)70852-5.

16. R. M. Karp, “On the Computational Complexity of Combinatorial Problems,” Networks, vol. 5, no. 1, pp. 45–68, 1975, doi: 10.1002/net.1975.5.1.45.

17. E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959, doi: 10.1007/BF01386390.

18. F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.

19. M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem,” Combinatorica, vol. 13, pp. 97–107, 1993, doi: 10.1007/BF01202792.

20. N. Robertson and P. D. Seymour, “Graph Minors. XIII. The Disjoint Paths Problem,” Journal of Combinatorial Theory, Series B, vol. 63, no. 1, pp. 65–110, 1995, doi: 10.1006/jctb.1995.1006.

21. N. Alon and M. Capalbo, “Finding Disjoint Paths in Expanders Deterministically and Online,” in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007, pp. 518–524, doi: 10.1109/FOCS.2007.19.

22. D. Wagner and K. Weihe, “A linear-time algorithm for edge-disjoint paths in planar graphs,” Combinatorica, vol. 15, no. 1, pp. 135–150, 1995, doi: 10.1007/BF01294465.