Two moves per time step make a difference

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
2 Downloads (Pure)

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(n1.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 Ω(n2) 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.

Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Electronic)9783959771092
DOIs
Publication statusPublished - 1 Jul 2019
Externally publishedYes
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: 9 Jul 201912 Jul 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period9/07/1912/07/19

Keywords

  • Algorithmic Graph Theory
  • NP-Complete Problem
  • Temporal Graph Exploration

Cite this

Erlebach, T., Kammer, F., Luo, K., Sajenko, A., & Spooner, J. T. (2019). Two moves per time step make a difference. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [141] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.141