Some polynomial subclasses of the Eulerian walk problem for a multiple graph

A. V. Smirnov

Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 3, pp. 338-356.

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. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in the graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by $k$ indices of the ordinary edges reachability sets, which are incident to some multi-edge.

Détail

Keywords: multiple graph, covering trails, edge-disjoint paths, Eulerian trail, eulerian cycle, graph with quasi-vertices, ordinary edges reachability set, polynomial subclass.
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, A. V. Smirnov, “Flows in multiple networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68 (in Russian)

[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, D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962, 216 pp. | MR | Zbl

[5] V. S. Roublev, 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 (in Russian) | 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 (in Russian) | 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 (in German) | DOI | MR

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

[10] Z. Lonc, 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, A. Silva, “Eulerian walks in temporal graphs”, Algoritmica, 85:3 (2023), 805–830 | DOI | MR | Zbl

[12] S. W. Bent, 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 | DOI

[14] A. V. Smirnov, “NP-completeness of the Eulerian walk problem for a multiple graph”, Modeling and Analysis of Information Systems, 31:1 (2024), 102–114 (in Russian) | DOI | Zbl

[15] J. Abrham, A. Kotzig, “Transformations of Euler tours”, Annals of Discrete Mathematics, 8 (1980), 65–69 | DOI | MR | Zbl

[16] R. M. Karp, “On the computational complexity of combinatorial problems”, Networks, 5:1 (1975), 45–68 | DOI | Zbl

[17] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1:1 (1959), 269–271 | DOI | MR | Zbl

[18] F. Harary, Graph theory, Addison-Wesley Pub. Co., 1969, 274 pp. | MR | Zbl

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

[20] N. Robertson, P. D. Seymour, “Graph minors. XIII. The disjoint paths problem”, Journal of Combinatorial Theory, Series B, 63:1 (1995), 65–110 | DOI | MR | Zbl

[21] N. Alon, M. Capalbo, “Finding disjoint paths in expanders deterministically and online”, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCST07), 2007, 518–524 | DOI

[22] D. Wagner, K. Weihe, “A linear-time algorithm for edge-disjoint paths in planar graphs”, Combinatorica, 15:1 (1995), 135–150 | DOI | MR | Zbl