Preview

Modeling and Analysis of Information Systems

Advanced search

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

https://doi.org/10.18255/1818-1015-2024-3-338-356

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. 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.

About the Author

Alexander V. Smirnov
P.G. Demidov Yaroslavl State University
Russian Federation


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, 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.


Review

For citations:


Smirnov A.V. Some polynomial subclasses of the Eulerian walk problem for a multiple graph. Modeling and Analysis of Information Systems. 2024;31(3):338-356. (In Russ.) https://doi.org/10.18255/1818-1015-2024-3-338-356

Views: 134


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)