Abstract
An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph G at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph \((G,\lambda )\), with \(\lambda : E(G)\rightarrow 2^{[\tau ]}\), an edge \(e\in E(G)\) is available only at the times specified by \(\lambda (e)\subseteq [\tau ]\), in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this scenario, even though several translations of Eulerian trails and walks are possible in temporal terms, only a very particular variation has been exploited in the literature, specifically for infinite dynamic networks (Orlin, 1984). In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether \((G,\lambda )\) has a temporal walk or trail is polynomial, while deciding whether it has a local trail is \(\textsf {NP}\)-complete even if it has lifetime 2. In contrast, in the general case, solving any of these problems is \(\textsf {NP}\)-complete, even under very strict hypotheses.
Partially supported by MIUR under PRIN Project n. 20174LF3T8 AHeAD (Efficient Algorithms for HArnessing Networked Data), University of Florence under Project GRANTED (GRaph Algorithms for Networked TEmporal Data), CNPq 303803/2020-7 and 437841/2018-9, FUNCAP/CNPq PNE-0112-00061.01.00/16, and STIC-AMSUD 360/2019 - 88881.197438/2018-01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This is the reason why we use the term dynamic-based, as they are similar to the dynamic networks used in [21] when studying Eulerian trails, except that edges cannot go back in time and the lifetime is finite.
References
Eleni, C.A., Mertzios, G.B., Spirakis, P.G.: The temporal explorer who returns to the base. In: 11th International Conference on Algorithms and Complexity - CIAC 2019, Rome, Italy, pp. 13–24 (2019)
Arumugam, S., Hamid, I., Abraham, V.M.: Decomposition of graphs into paths and cycles. J. Discrete Math. (2013)
Borgnat, P., Fleury, E., Guillaume, J-P., Magnien, C., Robardet, C., Scherrer, A.: Evolving networks. In: Mining Massive Data Sets for Security, pp. 198–203 (2007)
Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. In: Proceedings of Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, Canada, 5–7July 2020 (2021). To appear
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387–408 (2012)
Kayacı Çodur, M., Yılmaz, M.: A time-dependent hierarchical Chinese postman problem. Central Euro. J. Oper. Res. 28(1), 337–366 (2018). https://doi.org/10.1007/s10100-018-0598-8
Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized complexity of Eulerian deletion problems. Algorithmica 68(1), 41–61 (2014)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)
Erlebach, T., Hoffmann, M., Kammer, F.: In: 42nd International Colloquium on Automata, Languages, and Programming - ICALP 2015, Kyoto, Japan, volume 9134 of Lecture Notes in Computer Science, pp. 444–455. Springer (2015)
Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs. In: 43rd International Symposium on Mathematical Foundations of Computer Science - MFCS 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Erlebach, T., Spooner, J.T.: Non-strict temporal exploration. In: Richa, A.W., Scheideler, C. (eds.) SIROCCO 2020. LNCS, vol. 12156, pp. 129–145. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-54921-3_8
Fomin, F.V., Golovach, P.A.: Long circuits and large Euler subgraphs. SIAM J. Discrete Math. 28(2), 878–892 (2014)
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704–714 (1976)
Gómez, R., Wakabayashi, Y.: Covering a graph with nontrivial vertex-disjoint paths: existence and optimization. In: International Workshop on Graph-Theoretic Concepts in Computer Science - WG 2018, Cottbus, Germany, 27–29 June, pp. 228–238. Springer (2018)
Guan, M.: Graphic programming using odd or even points. Acta Math. Sin. (in Chinese), 10, 263–266 (1960). Translated in Chinese Mathematics 1. American Mathematical Society, 273–277
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. In: 32nd annual ACM Symposium on Theory of Computing - STOC 2000, Portland, Oregon, 21–23 May 2000
Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Mining 8(1), 1–29 (2018). https://doi.org/10.1007/s13278-018-0537-7
Manuel, P.: Revisiting path-type covering and partitioning problems. arXiv preprint arXiv:1807.10613 (2018)
Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4), 239–280 (2016)
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 63(4), 1–23 (2016)
Orlin, J.B.: Some problems on dynamic/periodic graphs. In: Progress in Combinatorial Optimization, pp. 273–293. Elsevier (1984)
Sun, J., Tan, G., Honglei, Q.: Dynamic programming algorithm for the time dependent Chinese postman problem. J. Inf. Comput. Sci. 8, 833–841 (2011)
Wang, H.-F., Wen, Y.-P.: Time-constrained Chinese postman problems. Comput. Math. Appl. 44(3–4), 375–387 (2002)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Marino, A., Silva, A. (2021). Königsberg Sightseeing: Eulerian Walks in Temporal Graphs. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms. IWOCA 2021. Lecture Notes in Computer Science(), vol 12757. Springer, Cham. https://doi.org/10.1007/978-3-030-79987-8_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-79987-8_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79986-1
Online ISBN: 978-3-030-79987-8
eBook Packages: Computer ScienceComputer Science (R0)