2026-07-21T12:32:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26250 2026-06-24T05:03:52Z ddc:004 open_access

On Sufficient Conditions for Short Journeys in Temporal Graphs Ilcinkas, David Morawietz, Nils Toullalan, Antoine Graph Theory Temporal Graph Temporal Graph Exploration 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Ilcinkas and Nils Morawietz and Antoine Toullalan 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.16 urn:nbn:de:0030-drops-262502 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.16 eng https://creativecommons.org/licenses/by/4.0/legalcode