DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2026.16

On Sufficient Conditions for Short Journeys in Temporal Graphs

Authors: David Ilcinkas, Nils Morawietz, and Antoine Toullalan

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

A temporal graph is defined as a sequence (G₁, G₂, …, G_L) of static graphs on a common set of n vertices. A strict journey in a temporal graph is the temporal analogue of a path in a static graph, in which at most one edge may be traversed at each time step. There exists a notable connection between the existence of paths in static graphs and the existence of strict journeys in specific temporal graphs. A well-known folklore result, commonly referred to as the Reachability Lemma, states that for two vertices u and v, if there are at least n-1 time steps during which a path connects u and v, then a strict journey from u to v exists. Our main theorem extends this lemma. Under the same assumptions as those of the Reachability Lemma, we prove that a strict journey from u to v exists and the number of edges traversed by such a journey admits a non-trivial upper bound. Furthermore, this bound converges toward the average length of the paths connecting u and v as the number of such paths increases. A corresponding lower bound is also established. In the second part of this work, we investigate the setting in which every path connecting vertices u and v has length at most a given integer k. For an integer b ≥ k, we characterize the sufficient number of time steps containing such a path that guarantees the existence of a journey from u to v traversing at most b edges. We derive an upper bound of ⌊(n-k-1)/(b-k+1) ⋅ (b-1)⌋ + k, and a lower bound of ⌊(n-k-1)/(b -k+1)⌋ ⋅ (b-1) + r + k-1, where r = (n-k-1 mod (b-k+1)). Finally, we present several applications of the first theorem, with particular emphasis on always connected temporal graphs, that is, temporal graphs where at each time step the graph is connected.

Cite as

David Ilcinkas, Nils Morawietz, and Antoine Toullalan. On Sufficient Conditions for Short Journeys in Temporal Graphs. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ilcinkas_et_al:LIPIcs.SAND.2026.16,
  author =	{Ilcinkas, David and Morawietz, Nils and Toullalan, Antoine},
  title =	{{On Sufficient Conditions for Short Journeys in Temporal Graphs}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.16},
  URN =		{urn:nbn:de:0030-drops-262502},
  doi =		{10.4230/LIPIcs.SAND.2026.16},
  annote =	{Keywords: Graph Theory, Temporal Graph, Temporal Graph Exploration}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2025.18

Brief Announcement: The Shortest Temporal Exploration Problem

Authors: Stefan Balev, Éric Sanlaville, and Antoine Toullalan

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

A temporal graph is a graph for which the edge set can change from one time step to the next. This paper considers undirected temporal graphs defined over L time steps and connected at each time step. We study the Shortest Temporal Exploration Problem (STEXP) that, given the evolution of the graph, asks for a temporal walk that starts at a given vertex, moves over at most one edge at each time step, visits all the vertices, takes at most L time steps and traverses the smallest number of edges. We prove that every constantly connected temporal graph with n vertices can be explored with O(n^{1.5}) edges traversed if L is O(n^{3.5}) time steps. This result improves the upper bound of O(n²) edges when L is Ω(n²). Moreover, we study the case where the graph has a diameter bounded by a parameter k at each time step and we prove that there exists an exploration which takes O(kn²) time steps and traverses O(kn) edges. Finally, the case where the underlying graph is a cycle is studied and tight linear bounds are provided on the number of edges traversed in the worst-case.

Cite as

Stefan Balev, Éric Sanlaville, and Antoine Toullalan. Brief Announcement: The Shortest Temporal Exploration Problem. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 18:1-18:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balev_et_al:LIPIcs.SAND.2025.18,
  author =	{Balev, Stefan and Sanlaville, \'{E}ric and Toullalan, Antoine},
  title =	{{Brief Announcement: The Shortest Temporal Exploration Problem}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{18:1--18:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.18},
  URN =		{urn:nbn:de:0030-drops-230716},
  doi =		{10.4230/LIPIcs.SAND.2025.18},
  annote =	{Keywords: Graph Theory, Temporal Graph, Temporal Graph Exploration}
}

Search Results

Documents authored by Toullalan, Antoine

On Sufficient Conditions for Short Journeys in Temporal Graphs

Abstract

Cite as

Brief Announcement: The Shortest Temporal Exploration Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message