NP-completeness of the Eulerian walk problem for a multiple graph
https://doi.org/10.18255/1818-1015-2024-1-102-114
Abstract
In this paper, we study undirected multiple graphs of any natural multiplicity $k>1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect 2 or $(k+1)$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge.
We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. We prove that the recognition variant of the multiple eulerian walk problem is NP-complete. For this purpose we first prove NP-completeness of the auxiliary problem of recognising the covering trails with given endpoints in an ordinary graph.
We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. We prove that the recognition variant of the multiple eulerian walk problem is NP-complete. For this purpose we first prove NP-completeness of the auxiliary problem of recognising the covering trails with given endpoints in an ordinary graph.
Keywords
multiple graph,
multiple path,
divisible graph,
covering trails,
edge-disjoint paths,
eulerian trail,
eulerian cycle,
NP-completeness
MSC2020: 05C45, 05C65
References
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.
14. 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.
15. M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem,” Combinatorica, vol. 13, pp. 97–107, 1993, doi: 10.1007/BF01202792.
Review
For citations:
Smirnov A.V. NP-completeness of the Eulerian walk problem for a multiple graph. Modeling and Analysis of Information Systems. 2024;31(1):102-114. (In Russ.) https://doi.org/10.18255/1818-1015-2024-1-102-114
Views:
226
Email this article 