NP-completeness of the Eulerian walk problem for a multiple graph

A. V. Smirnov

Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 1, pp. 102-114.

Résumé

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.

Détail

Keywords: multiple graph, multiple path, covering trails, edge-disjoint paths, eulerian trail, eulerian cycle, NP-completeness.
Mots-clés : divisible graph

Bibliographie

[1] A. V. Smirnov, “The Shortest Path Problem for a Multiple Graph”, Automatic Control and Computer Sciences, 52:7 (2018), 625–633 | DOI | MR

[2] V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68

[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, 50:7 (2016), 527–535 | DOI

[4] L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962 | MR | Zbl

[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, 17:2 (2010), 72–98 | MR

[6] A. V. Smirnov, “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix”, Automatic Control and Computer Sciences, 51:7 (2017), 558–566 | DOI | MR

[7] A. V. Smirnov, “The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph”, Modeling and Analysis of Information Systems, 30:3 (2023), 264–282 | DOI | MR | Zbl

[8] C. Hierholzer, “Über die Móglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren”, Mathematische Annalen, 6:1 (1873), 30–32 | DOI | MR

[9] C. Berge, Graphs and Hypergraphs, North-Holland Publishing Company, 1973 | MR | Zbl

[10] Z. Lonc and P. Naroski, “On Tours that contain all Edges of a Hypergraph”, The Electronic Journal of Combinatorics, 17 (2010), R144 | DOI | MR | Zbl

[11] A. Marino and A. Silva, “Eulerian Walks in Temporal Graphs”, Algoritmica, 85:3 (2023), 805–830 | DOI | MR | Zbl

[12] S. W. Bent and U. Manber, “On non-intersecting Eulerian circuits”, Discrete Applied Mathematics, 18:1 (1987), 87–94 | DOI | MR | Zbl

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

[14] R. M. Karp, “On the Computational Complexity of Combinatorial Problems”, Networks, 5:1 (1975), 45–68 | DOI | Zbl

[15] M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem”, Combinatorica, 13 (1993), 97–107 | DOI | MR | Zbl