LIPIcs.SAND.2023.13.pdf
- Filesize: 0.69 MB
- 15 pages
Document
Restless Exploration of Periodic Temporal Graphs
Authors
-
Part of:
Volume:
2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-06-12
Cite As Get BibTex
Thomas Bellitto, Cyril Conchon-Kerjan, and Bruno Escoffier. Restless Exploration of Periodic Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SAND.2023.13
Abstract
A temporal graph is a sequence of graphs, indexed by discrete time steps, with a fixed vertex set but with an edge set that is able to change over time. In the temporal graph exploration problem, an agent wants to visit all the vertices of a given temporal graph. In the classical model, at each time step the agent can either stay where they are, or move along one edge. In this work we add a constraint called restlessness that forces the agent to move along one edge at each time step. We mainly focus on (infinite) periodical temporal graphs. We show that if the period is 2 one can decide in polynomial time whether exploring the whole graph is possible or not, while this problem turns out to be NP-hard for any period p ≥ 3. We also show some time bounds on the explorations of such graphs when the exploration is possible.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Temporal graphs
- Graph exploration
- NP-completeness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. Springer, 2009.
- Piotr Berman, Marek Karpinski, and Alex D. Scott. Approximation hardness of short symmetric instances of MAX-3SAT. Electron. Colloquium Comput. Complex., TR03-049, 2003. URL: https://arxiv.org/abs/TR03-049.
- Hans L. Bodlaender and Tom C. van der Zanden. On exploring always-connected temporal graphs of small pathwidth. Inf. Process. Lett., 142:68-71, 2019. URL: https://doi.org/10.1016/j.ipl.2018.10.016.
- Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. Algorithmica, 83(9):2754-2802, 2021. URL: https://doi.org/10.1007/s00453-021-00831-w.
- Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. J. Comput. Syst. Sci., 119:1-18, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.005.
- Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two moves per time step make a difference. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 141:1-141:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.141.
- Thomas Erlebach and Jakob T. Spooner. Parameterized temporal exploration problems. In James Aspnes and Othon Michail, editors, 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference, volume 221 of LIPIcs, pages 15:1-15:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.SAND.2022.15.
- Petter Holme. Temporal network structures controlling disease spreading. Phys. Rev. E, 94:022305, August 2016. URL: https://doi.org/10.1103/PhysRevE.94.022305.
- David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade. Exploration of constantly connected dynamic graphs based on cactuses. In Magnús M. Halldórsson, editor, Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, volume 8576 of Lecture Notes in Computer Science, pages 250-262. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-09620-9_20.
- Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theor. Comput. Sci., 634:1-23, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.006.