Two Moves per Time Step Make a Difference

Authors Thomas Erlebach , Frank Kammer , Kelin Luo , Andrej Sajenko , Jakob T. Spooner



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.141.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Erlebach
  • Department of Informatics, University of Leicester, Leicester, England
Frank Kammer
  • THM, University of Applied Sciences Mittelhessen, Giessen, Germany
Kelin Luo
  • School of Management, Xi'an Jiaotong University, Xianning West Road, Xi'an, China
Andrej Sajenko
  • THM, University of Applied Sciences Mittelhessen, Giessen, Germany
Jakob T. Spooner
  • Department of Informatics, University of Leicester, Leicester, England

Acknowledgements

We would like to thank an anonymous reviewer for a helpful suggestion regarding the presentation of the proof of one of the lemmas.

Cite AsGet BibTex

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two Moves per Time Step Make a Difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.141

Abstract

A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Temporal Graph Exploration
  • Algorithmic Graph Theory
  • NP-Complete Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The Complexity of Optimal Design of Temporally Connected Graphs. Theory of Computing Systems, 61(3):907-944, 2017. URL: http://dx.doi.org/10.1007/s00224-017-9757-x.
  2. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal Vertex Cover with a Sliding Time Window. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of LIPIcs, pages 148:1-148:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.148.
  3. Björn Brodén, Mikael Hammar, and Bengt J. Nilsson. Online and Offline Algorithms for the Time-Dependent TSP with Time Zones. Algorithmica, 39(4):299-319, 2004. URL: http://dx.doi.org/10.1007/s00453-004-1088-z.
  4. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. URL: http://dx.doi.org/10.1080/17445760.2012.668546.
  5. Giuseppe Antonio Di Luna, Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Live Exploration of Dynamic Rings. In Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS 2016), pages 570-579. IEEE Computer Society, 2016. URL: http://dx.doi.org/10.1109/ICDCS.2016.59.
  6. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On Temporal Graph Exploration. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Part I, volume 9134 of LNCS, pages 444-455. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_36.
  7. Thomas Erlebach and Jakob T. Spooner. Faster Exploration of Degree-Bounded Temporal Graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 36:1-36:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2018.36.
  8. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche. Temporal Graph Classes: A View Through Temporal Separators. In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), volume 11159 of LNCS, pages 216-227. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-030-00256-5_18.
  9. M. R. Garey, David S. Johnson, and Robert Endre Tarjan. The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5(4):704-714, 1976. URL: http://dx.doi.org/10.1137/0205049.
  10. David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses. In Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), volume 8576 of LNCS, pages 250-262. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-09620-9_20.
  11. David Ilcinkas and Ahmed Mouhamadou Wade. Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring. Theory of Computing Systems, 62(5):1144-1160, 2018. URL: http://dx.doi.org/10.1007/s00224-017-9796-3.
  12. Othon Michail. An Introduction to Temporal Graphs: An Algorithmic Perspective. Internet Mathematics, 12(4):239-280, 2016. URL: http://dx.doi.org/10.1080/15427951.2016.1177801.
  13. Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.04.006.
  14. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 61(2):72, 2018. URL: http://dx.doi.org/10.1145/3156693.
  15. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The Complexity of Finding Small Separators in Temporal Graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 45:1-45:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2018.45.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail