On Sufficient Conditions for Short Journeys in Temporal Graphs

Ilcinkas, David; Morawietz, Nils; Toullalan, Antoine

doi:10.4230/LIPIcs.SAND.2026.16

On Sufficient Conditions for Short Journeys in Temporal Graphs

David Ilcinkas

Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France Nils Morawietz

Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France
Institute of Computer Science, Friedrich Schiller University Jena, Germany Antoine Toullalan

Université Le Havre Normandie, Univ Rouen Normandie, INSA Rouen Normandie, Normandie Univ, LITIS UR 4108, F-76600 Le Havre, France

Abstract

A temporal graph is defined as a sequence $(G_{1},G_{2},\dots,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\geq 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 $\left\lfloor\frac{n-k-1}{b-k+1}\cdot(b-1)\right\rfloor+k$ , and a lower bound of $\left\lfloor\frac{n-k-1}{\,b-k+1\,}\right\rfloor\cdot(b-1)\;+\;r\;+\;k-1$ , where $r=(n-k-1\bmod(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.

Keywords and phrases:

Graph Theory, Temporal Graph, Temporal Graph Exploration

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Graph theory

Funding:

This work was supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL).

DOI:

10.4230/LIPIcs.SAND.2026.16

Event:

5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Editors:

George B. Mertzios and Andréa W. Richa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

An important tool for modeling networks is graph theory. However, many real-world networks evolve over time, as connections may appear or disappear – for instance, in railway systems or social networks – and therefore cannot be adequately represented by classical static graphs. To capture such dynamics, temporal graphs have been introduced. In these models, each edge is associated with the time steps at which it is present. In recent years, temporal graphs have attracted significant attention in the study of complexity-theoretic problems [3, 8, 18], combinatorial problems [24], and reachability problems [2, 4, 19]. We refer the reader to the surveys [10, 25] for an overview of the area.

More formally, a temporal graph $\mathcal{G}$ with lifetime $L$ is typically defined as a sequence of undirected graphs $(G_{1},G_{2},\dots,G_{L})$ , called snapshots, that share a common vertex set of size $n$ . A temporal edge is an edge that appears at a given time step. Since the edge set may vary over time, the classical notion of a path must be adapted to prevent the traversal of edges at time steps when they are absent.

In a temporal graph, the analogue of a path connecting two vertices $u$ and $v$ is a journey (also referred to as a temporal walk), defined as a sequence of temporal edges from $u$ to $v$ whose time labels are non-decreasing. A journey is said to be strict if it traverses at most one edge per time step; otherwise, it is non-strict.

While a journey generalizes the concept of a path in static graphs, there is no unique analogue to the notion of a shortest path in temporal graphs, as several optimization criteria may be considered. In particular, one may minimize the number of edges traversed (shortest journeys), the arrival time (foremost journeys), or the duration between departure and arrival (fastest journeys). These criteria are examined in greater detail in the work of Bui Xuan et al. [30]. Numerous reachability problems have been investigated in temporal graphs [15, 22, 29, 27] where the objective is to compute a journey satisfying specified properties. Also, Casteigts et al. [9] proposed a hierarchy of temporal graphs based on their expressivity, they prove that these families are associated to different reachability properties.

One of the most widely studied problems in this area is the Temporal Exploration Problem (TEXP) [1, 6, 13, 15, 16, 17, 21, 20, 26, 5], which was formally introduced and named by Michail et al. [26]. The objective of TEXP is to determine a journey that visits all vertices of a temporal graph. Deciding whether such a temporal exploration exists is NP-hard in the general case [26].

This hardness result has motivated the study of TEXP on always connected temporal graphs, namely temporal graphs that are connected at every time step [1, 6, 15, 16, 17, 20, 21]. These graphs have received particular attention because any always connected temporal graph can be explored within $(n-1)^{2}$ time steps [26]. This bound is a corollary of the folklore result known as the Reachability Lemma, first introduced by Kuhn et al. [23] in the context of dynamic networks and later formalized by Erlebach et al. [15]. The lemma states that if two vertices $u$ and $v$ are connected by a path during at least $n-1$ distinct time steps, then there exists a strict journey from $u$ to $v$ over these time steps.

For always connected temporal graphs, a substantial body of work has focused on variants of TEXP that minimize the arrival time, referred to as foremost temporal exploration [15, 20, 1, 21, 17, 16, 7]. More recently, attention has also been given to variants of TEXP that minimize the number of edges traversed, known as shortest temporal exploration [6].

Another extensively studied class of reachability problems in temporal graphs concerns the computation of journeys that optimize at least one of the three criteria introduced above. Wu et al. [28] proposed pseudo-polynomial algorithms for computing shortest, foremost, and fastest strict journeys in general temporal graphs. The case where the temporal graph is directed at every time step was investigated by Cheng [11], who presented a pseudo-polynomial algorithm for computing shortest journeys. Enright et al. [14] present complexity results on the problem of counting the number of foremost and fastest journeys between two vertices. Danda et al. [12] studied a bicriteria optimization problem that consists of finding, among all fastest journeys, one that is shortest. We note that the notion of a shortest journey adopted by Danda et al. [12] differs from the definition used in this article: in their model, each temporal edge is associated with a traversal time that may exceed one time step, so a shortest journey is defined as one that minimizes the total sum of traversal times.

While significant research efforts have focused on the complexity analysis of these problems and on the development of efficient algorithms, comparatively little work has addressed the combinatorial bounds associated with shortest, foremost, and fastest journeys. Notable contributions adopting such a combinatorial viewpoint include the work of Erlebach et al. [15], which formalized the Reachability Lemma, and the work of Balev et al. [6], which establishes that if there exist $k n$ time steps during which two vertices $u$ and $v$ are connected by a path of length at most $k$ , then there exists a strict journey from $u$ to $v$ whose length is at most $k$ . Bastide et al. [7] refine the Reachability Lemma by studying the connectivity within sets of vertices in always-connected temporal graphs. In this paper, we extend these results by characterizing the length (that is, the number of edges traversed) of the shortest strict journey between two vertices that are connected by paths during $\tau$ time steps, where $\tau\geq n-1$ . In this regime, the existence of a strict journey is guaranteed by the Reachability Lemma.

Our results.

In Section 3, we present our main result, namely Theorem 3.4, which extends the well-known “Reachability Lemma”. This theorem states that, in a temporal graph, if there exists a set $T$ of time steps with $|T|\geq n-1$ such that, for every $t\in T$ , the vertices $u$ and $v$ are connected by a path, and if the average length of these paths is $k$ , then there exists a strict journey from $u$ to $v$ that traverses at most $\lfloor\frac{|T|}{|T|-n+2}(k-2)\rfloor+2$ edges. In particular, this bound converges rapidly to the average path length $k$ as the number of time steps in $T$ increases.

We then consider a restricted case in which every path connecting $u$ and $v$ has length at most a fixed integer $k$ . We prove that, given the integers $k$ and $b$ such that $1<k\leq b<n$ , the number of time steps containing a path of length $k$ between $u$ and $v$ that is sufficient to guarantee the existence of a strict journey of length at most $b$ is at most $\left\lfloor\frac{n-k-1}{b-k+1}\cdot(b-1)\right\rfloor+k.$

In Section 4, we establish lower bounds to the sufficient conditions derived in Section 3. For the restricted case, for given integers $n$ , $k$ , and $b$ , we construct a family of temporal graphs on $n$ vertices such that the shortest journey from $u$ to $v$ has length strictly larger than $b$ although $u$ and $v$ are connected by a path of length exactly $k$ in many time steps. The obtained lower bound on the sufficient number of paths of length at most $k$ to guarantee a journey of length at most $b$ is $\left\lfloor\frac{n-k-1}{\,b-k+1\,}\right\rfloor\cdot(b-1)\;+\;r\;+\;k-1$ , where $r=(n-k-1\bmod(b-k+1))$ . In this restricted case, the upper and lower bounds are tight whenever $n-k-1$ is a multiple of $b-k+1$ .

We derive a non-trivial lower bound corresponding to the main theorem. More precisely, for parameters $n>0$ and $k<\sqrt{n/2}$ , we construct a temporal graph on $n$ vertices and a set $T$ of time steps with $|T|>4(n-2)$ such that, for every $t\in T$ , the vertices $u$ and $v$ are connected by a path and the average length of these paths is $k$ . In this construction, the shortest journey from $u$ to $v$ has length $\left\lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+1$ .

Finally, in Section 5, we present several applications of the main theorem. We focus on always connected temporal graphs and establish an upper bound on the temporal diameter, defined as the maximum length of a shortest journey, in the case where each snapshot has diameter at most $k$ . We then derive analogous results for the case where each snapshot has bounded average shortest-path length, as well as for the case where there exists a vertex $u$ whose closeness centrality is bounded in every snapshot.

2 Preliminaries

Firstly, we give a formal definition of temporal graphs.

Definition 2.1 (Temporal graph).

A temporal graph $\mathcal{G}$ with a vertex set $V$ and a lifetime $L$ is a sequence of static graphs $(G_{1},G_{2},\dots,G_{L})$ where $G_{i}=(V,E_{i})$ is called the snapshot at the time step $i\in[1,L]$ . The underlying graph of $\mathcal{G}$ is $G=(V,E)$ with $V$ the vertex set of $\mathcal{G}$ and $E$ the union of the edge sets of all the snapshots of $\mathcal{G}$ .

Note that the initial time step is time step $1$ .

We now introduce the classical notion of a path in a snapshot.

Definition 2.2 (Path).

Let $\mathcal{G}$ be a temporal graph. A path between the vertices $u\in V$ and $v\in V$ at the time step $t$ is a sequence of vertices $(w_{0},w_{1},\dots,w_{l})$ such that $\forall\,i\in[0,l-1],w_{i}w_{i+1}\in E_{t}$ , $w_{0}=u$ and $w_{l}=v$ . The length of the path is the number $l$ of edges.

Next, we present the definition of a strict journey in a temporal graph, which is the temporal equivalent of a path.

Definition 2.3 (Strict Journey).

Let $\mathcal{G}$ be a temporal graph. A strict journey from a vertex $u\in V$ to a vertex $v\in V$ is a sequence $((v_{0}v_{1},t_{1}),(v_{1}v_{2},t_{2}),\dots,(v_{l-1}v_{l},t_{l}))$ such that:

$\blacksquare$

$t_{1}<t_{2}<\dots<t_{l}$ (strictly increasing time steps),
$\blacksquare$

$v_{i}v_{i+1}\in E_{t_{i}}$ for every $i\in[0,l-1]$ ,
$\blacksquare$

$v_{0}=u$ and $v_{l}=v$ .

In other words, an agent can move from $u$ to $v$ by traversing the edges in the given order at the specified time steps. The length of the journey is $l$ , i.e., the number of edges traversed.

In this paper, we focus on strict journeys of minimum length, that is, journeys minimizing the number of traversed edges. Since only strict journeys are considered, the term journey will henceforth refer to a strict journey.

We now recall the “Reachability Lemma”.

Lemma 2.4 (Reachability Lemma [15]).

Let $\mathcal{G}$ be a temporal graph with vertex set $V$ , and let $u,v\in V$ be two distinct vertices. If there exist $n-1$ time steps at which $u$ and $v$ are connected by a path, then there exists a strict journey from $u$ to $v$ .

The intuition behind the proof is the following. Consider a time step $t$ at which $u$ and $v$ are connected by a path in $G_{t}$ . If $v$ is not reachable from $u$ at time $t$ , then there must exist a vertex $w$ on this path that is not yet reachable from $u$ at time $t$ , but that is adjacent to a vertex $w^{\prime}$ which is reachable from $u$ at time $t$ (that is, there exists a journey from $u$ to $w^{\prime}$ with arrival time at most $t$ ). Consequently, vertex $w$ becomes reachable from $u$ at time $t+1$ . So after $n-1$ such time steps, there is a strict journey from $u$ to $v$ . A more formal proof is the proof of Lemma 2.1 in this article by Erlebach et al. [15].

In the final section, applications of Theorem 3.4 are presented, establishing bounds on various topological and centrality measures in always connected temporal graphs. In particular, closeness centrality in this class of temporal graphs is studied. For this purpose, we recall the following definition of closeness centrality in static graphs.

Definition 2.5 (Closeness centrality (in static graphs)).

Let $G=(V,E)$ be a connected static graph with $n$ vertices. The closeness centrality of the vertex $u$ is $C(u)=\frac{n-1}{\sum_{v\in V}d(u,v)}$ with $d(u,v)$ the length of a shortest path connecting $u$ and $v$ .

Throughout this paper, we adopt the following notations. Let $u$ and $v$ be two vertices and let $t$ be a time step. A path in a snapshot between $u$ and $v$ is denoted by $u\leftrightarrow v$ . If this path appears in the snapshot at time step $t$ and has a length at most $k$ , we write $u\leftrightarrow_{(k,t)}v$ , or simply $u\leftrightarrow_{k}v$ when no ambiguity arises. Similarly, a journey $J$ from $u$ to $v$ consisting of at most $b$ edges is denoted by $u\rightsquigarrow_{b}v$ , and its length (i.e., its number of edges traversed) is denoted by $|J|$ . If, in addition, the arrival time of such a journey is at most $t$ , we write $u\rightsquigarrow_{(b,t)}v$ . Furthermore, given a temporal graph with vertex set $V$ , a parameter $b$ , and a pair of vertices $(u,v)$ , we use the following notation. Let $n=|V|$ . For every vertex $w\in V$ and every time step $t$ , we define the local potential $\ell_{t}(w)$ .

\ell_{t}(w)=\begin{cases}b+1&\mbox{if there is no journey }u\rightsquigarrow_{% (b,t)}w\\ \min_{J:u\rightsquigarrow_{(b,t)}w}|J|&\mbox{otherwise }\end{cases}

Moreover, we associate with each time step $t$ the potential function $\Phi_{t}=\sum_{w\in V}\ell_{t}(w)$ and the set $A_{t}=\{w\in V\setminus\{v\}\mid\ell_{t}(w)=b+1\}$ . That is, $A_{t}$ contains those vertices $w$ (excluding $v$ ) for which there is no journey $u\rightsquigarrow_{(b,t)}w$ . By definition, for any $w$ and $t<L$ , we have $\ell_{t+1}(w)\leq\ell_{t}(w)$ , $\Phi_{t+1}\leq\Phi_{t}$ , and $A_{t+1}\subseteq A_{t}$ .

3 The sufficient conditions for short journeys

In this section, we establish sufficient conditions on the number and lengths of paths connecting two distinct vertices $u$ and $v$ to guarantee the existence of a journey from $u$ to $v$ that traverses at most $b$ edges. We first present general technical tools. They are used to obtain upper bounds on the length of the obtained journeys, and then on the number of paths of a given length that is sufficient to obtain a journey of a prescribed maximum length.

3.1 Technical Tools

We prove in this subsection that the potential must decrease between the steps $t$ and $t+1$ when there exists a path $u\leftrightarrow_{(b,t)}v$ and there is no journey $u\rightsquigarrow_{(b,t)}v$ . Without loss of generality, all the paths considered in this paper are elementary.

We start by describing the situation in the first time steps, in which the loss of potential is necessarily large. For example, at the very beginning, $\ell_{1}(w)=b+1$ for any vertex $w\neq u$ (recall that the initial time step is time step $1$ ). After one time step with a path from $u$ to $v$ , any neighbor $w$ of $u$ in that time step has local potential 1, and thus the potential loss is at least $b$ . The following lemma extends this observation to the first few such time steps.

Lemma 3.1.

Let $\mathcal{G}$ be a temporal graph on $n$ vertices, let $i$ and $b$ be integers that satisfy $1<i\leq b+1\leq n$ , and let $(u,v)$ be a pair of distinct vertices such that there is a path $u\leftrightarrow v$ at each time step. If $\ell_{i-1}(v)=b+1$ , then $\Phi_{i}\leq(n-i)b+\binom{i}{2}+|A_{i}|+1$ .

Proof.

We prove that the following proposition $\mathcal{P}({i^{\prime}})$ is true for ${i^{\prime}}\in[1,i]$ (it is the conjunction of two propositions).

\mathcal{P}({i^{\prime}}):\begin{cases}\forall\,w\in V,\ell_{i^{\prime}}(w)<{i% ^{\prime}}\text{ or }\ell_{i^{\prime}}(w)=b+1\\ \forall\,0\leq j<{i^{\prime}},\left|\left\{w\mid\ell_{i^{\prime}}(w)\leq j% \right\}\right|\geq j+1\end{cases}

Proposition $\mathcal{P}({i^{\prime}})$ describes the possible values of the local potentials at time step ${i^{\prime}}$ : any local potential smaller than $b+1$ must in fact be smaller than ${i^{\prime}}$ , and there are at least $j+1$ vertices with local potentials at most $j$ , for any $j<{i^{\prime}}$ .

We assume that $\ell_{i-1}(v)=b+1$ and we prove by induction that for any $1\leq{i^{\prime}}\leq i$ , $\mathcal{P}({i^{\prime}})$ holds. First $\mathcal{P}(1)$ holds because at $t=1$ , $\ell_{1}(u)=0$ and $\forall\,{w\in V\setminus\{u\}},\ell_{1}(w)=b+1$ , so $|\{w\mid\ell_{1}(w)\leq 0\}|\geq 1$ .

Let us assume now that $\mathcal{P}({i^{\prime}})$ holds, for some $1\leq{i^{\prime}}\leq i-1$ , and show that $\mathcal{P}({i^{\prime}}+1)$ holds. Let $a$ and $c$ be vertices in the path $u\leftrightarrow v$ at time step ${i^{\prime}}$ such that $c\notin\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}$ , $c$ is adjacent to $a$ at time step ${i^{\prime}}$ , and $a\in\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}$ . The vertices $a$ and $c$ exist on this path because $\ell_{i^{\prime}}(u)=0$ so $u\in\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}$ and $\ell_{i^{\prime}}(v)=b+1$ so $v\notin\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}$ . So at the time step ${i^{\prime}}+1$ , we have $\ell_{{i^{\prime}}+1}(c)\leq\ell_{i^{\prime}}(a)+1\leq{i^{\prime}}$ , and $|\{w\mid\ell_{{i^{\prime}}+1}(w)\leq{i^{\prime}}\}|\geq|\{w\mid\ell_{i^{\prime% }}(w)\leq{i^{\prime}}-1\}|+1\geq{i^{\prime}}+1$ because $c\notin\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}$ and $c\in\{w\mid\ell_{{i^{\prime}}+1}(w)\leq{i^{\prime}}\}$ , and by the induction hypothesis $|\{w\mid\ell_{i^{\prime}}(w)\leq{i^{\prime}}-1\}|\geq{i^{\prime}}$ .

Furthermore, by the induction hypothesis, any vertex $w$ satisfies $\ell_{i^{\prime}}(w)\in[1,{i^{\prime}}-1]\cup\{b+1\}$ . Therefore, any vertex $w$ satisfies $\ell_{{i^{\prime}}+1}(w)\in[1,{i^{\prime}}]\cup\{b+1\}$ . Since

\forall\,{0\leq j<{i^{\prime}}},|\{w\mid\ell_{{i^{\prime}}+1}(w)\leq j\}|\geq|% \{w\mid\ell_{{i^{\prime}}}(w)\leq j\}|\geq j+1

by the induction hypothesis, we finally have that $\mathcal{P}({i^{\prime}}+1)$ holds. So we have proven that $\mathcal{P}({i^{\prime}})$ holds for $1\leq{i^{\prime}}\leq i$ .

By proposition $\mathcal{P}(i)$ , at the time step $i$ there is a set $S$ of $i$ vertices such that

\sum_{w\in S}\ell_{i}(w)\leq 0+1+2+\dots+i-1=\binom{i}{2}

and

\forall{w\in V\setminus(S\cup A_{i}\cup\{v\})},\ell_{i}(w)\leq i-1

so $\Phi_{i}\leq(|A_{i}|+1)(b+1)+\binom{i}{2}+(n-(|A_{i}|+1)-i)(i-1)$ . Since $i-1\leq b$ , we obtain the desired inequality. $\hfill\blacktriangleleft$

The next lemma shows that the potential function $\Phi$ decreases at each time step $t$ during which there exists a path connecting $u$ and $v$ of length $d_{t}$ by at least some amount depending on $d_{t}$ , provided that no journey of length at most $b$ from $u$ to $v$ exists so far.

Lemma 3.2.

Let $\mathcal{G}$ be a temporal graph, and let $b$ be an integer such that $0<b<n$ . Suppose there exists a pair of distinct vertices $(u,v)$ and a time step $t>0$ such that there is a path $u\leftrightarrow v$ of length $d_{t}$ at time $t$ . If $\ell_{t}(v)=b+1$ , then $\Phi_{t}-\Phi_{t+1}\;\geq\;b-d_{t}+1\;+\;|A_{t}|-|A_{t+1}|$ .

Proof.

By assumption, there is a path $(w_{0},w_{1},\dots,w_{d_{t}})$ in $G_{t}$ with $w_{0}=u$ and $w_{d_{t}}=v$ . Let $f$ be minimum such that $\ell_{t}(w_{f})=b+1$ (it exists because $\ell_{t}(w_{d_{t}})=b+1$ ), and let $I=\left\{i\in[1,f]\mid\ell_{t}(w_{i-1})<\ell_{t}(w_{i})\right\}$ .

Given that $\ell_{t}(u)=0$ and $\ell_{t}(w_{f})=b+1$ , we have that $\sum_{i\in I}\left(\ell_{t}(w_{i})-\ell_{t}(w_{i-1})\right)\geq b+1$ (see Figure 1). By definition of the local potential, we have $\ell_{t+1}(w_{i})\leq\ell_{t}(w_{i-1})+1$ for each $i\in I$ . So we obtain

\sum_{i\in I}\ell_{t}(w_{i})-\sum_{i\in I}(\ell_{t+1}(w_{i})-1)\geq b+1\;,

and we deduce that

\sum_{i\in I}\ell_{t}(w_{i})-\sum_{i\in I}\ell_{t+1}(w_{i})\geq b+1-|I|\;.

Note that $|I|\leq f\leq d_{t}-|A_{t}\cap\{w_{f},\dots,w_{d_{t}-1}\}|$ (see Figure 1). Also, for any $w\in A_{t}\setminus(A_{t+1}\cup\{w_{f},\dots,w_{d_{t}-1}\})$ , we have $\ell_{t}(w)-\ell_{t+1}(w)\geq 1$ . Overall, since $A_{t+1}\subseteq A_{t}$ and $v\notin A_{t}$ , we have $(A_{t}\cap\{w_{f},\dots,w_{d_{t}-1}\})\cup(A_{t}\setminus(A_{t+1}\cup\{w_{f},% \dots,w_{d_{t}-1}\}))\supseteq A_{t}\setminus A_{t+1}$ . Note that the latter is a disjoint union. Based on this, we conclude

	$\displaystyle\Phi_{t}-\Phi_{t+1}$	$\displaystyle\geq\sum_{i\in I}\ell_{t}(w_{i})-\sum_{i\in I}\ell_{t+1}(w_{i})+% \sum_{w\notin\{w_{i}\mid i\in I\}}(\ell_{t}(w)-\ell_{t+1}(w))$
		$\displaystyle\geq b+1-\|I\|+\|A_{t}\setminus(A_{t+1}\cup\{w_{f},\dots,w_{d_{t}-1}% \})\|$
		$\displaystyle\geq b+1-d_{t}+\|A_{t}\cap\{w_{f},\dots,w_{d_{t}-1}\}\|+\|A_{t}% \setminus(A_{t+1}\cup\{w_{f},\dots,w_{d_{t}-1}\})\|$
		$\displaystyle\geq b-d_{t}+1+\|A_{t}\|-\|A_{t+1}\|.$

This completes the proof.

Figure 1: An example of a path

u\leftrightarrow_{(d_{t},t)}v

with

d_{t}>5

. All the directed edges

w_{i-1}w_{i}

with

i\in I

and the vertices in the set

A_{t}\cap\{w_{f},\dots,w_{d_{t}-1}\}

are represented in red.

$\hfill\blacktriangleleft$

Finally, we study what happens in the last time steps before there exists a journey $u\rightsquigarrow_{b}v$ . Intuitively, either the potential is still a bit large at the end, or more than the usual amount of potential was lost in the last steps. In order to express that more formally, we show that the potential cannot be too small a few time steps before a time step $t$ such that $\ell_{t}(v)=b+1$ . For example, at time $t-1$ , there must exist a vertex $w\neq v$ which has local potential at least $b$ and which prevented $v$ to lose potential between time $t-1$ and $t$ .

Lemma 3.3.

Let $\mathcal{G}$ be a temporal graph on $n$ vertices, let $i$ and $b$ be integers that satisfy $1<i\leq b+1\leq n$ , and let $(u,v)$ be a pair of distinct vertices such that there is a path $u\leftrightarrow v$ at each time step. Given a time step $t$ , if $t\geq i$ and $\ell_{t}(v)=b+1$ , then $\Phi_{t-i+1}\geq(b-i)i+\binom{i+1}{2}+|A_{t-i+1}|+n-1$ .

Proof.

Let $t\geq i$ with $\ell_{t}(v)=b+1$ .

In the first part, we prove by induction on ${i^{\prime}}$ that the following proposition $\mathcal{Q}({i^{\prime}})$ is true for each ${i^{\prime}}\in[1,i]$ . This proposition states that, for any $0\leq j<{i^{\prime}}$ , at least $j+1$ vertices have local potential at least $b+1-j$ at time $t+1-{i^{\prime}}$ .

\mathcal{Q}({i^{\prime}}):\forall\,0\leq j<{i^{\prime}},\left|\left\{w\mid\ell% _{t+1-{i^{\prime}}}(w)\geq b+1-j\right\}\right|\geq j+1

Firstly, $\mathcal{Q}(1)$ holds because at time $t$ , $\ell_{t}(v)=b+1$ , so $|\{w\mid\ell_{t}(w)\geq b+1\}|\geq 1$ .

Secondly, we assume that $\mathcal{Q}({i^{\prime}})$ holds for $1\leq{i^{\prime}}\leq i-1$ and we show that $\mathcal{Q}({i^{\prime}}+1)$ holds. By definition of $t$ , we have $t+1-({i^{\prime}}+1)=t-{i^{\prime}}\geq 1$ and $\ell_{t-{i^{\prime}}}(v)=b+1$ . Let $a$ and $c$ be vertices on the path $u\leftrightarrow v$ at time step $t-{i^{\prime}}$ such that $a\in\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}$ , $a$ is adjacent to $c$ at that time, and $c\notin\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}$ .
The vertices $a$ and $c$ exist on this path because $\ell_{t+1-{i^{\prime}}}(u)=0$ so $u\notin\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}$ and $\ell_{t+1-{i^{\prime}}}(v)=b+1$ so $v\in\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}$ . This implies that $\ell_{t+1-{i^{\prime}}}(a)\leq\ell_{t-{i^{\prime}}}(c)+1$ and we know that $\ell_{t+1-{i^{\prime}}}(a)\geq b-{i^{\prime}}+2$ . Hence, $\ell_{t-{i^{\prime}}}(c)\geq b-{i^{\prime}}+1$ .

So

|\{w\mid\ell_{t-{i^{\prime}}}(w)\geq b-{i^{\prime}}+1\}|\geq|\{w\mid\ell_{t+1-% {i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}|+1\geq{i^{\prime}}+1

since $c\notin\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}$ and $c\in\{w\mid\ell_{t-{i^{\prime}}}(w)\geq b-{i^{\prime}}+1\}$ and by the induction hypothesis, $|\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-{i^{\prime}}+2\}|\geq{i^{\prime}}$ . Moreover, by the induction hypothesis,

\forall{1\leq j<{i^{\prime}}},|\{w\mid\ell_{t-{i^{\prime}}}(w)\geq b-j+1\}|% \geq|\{w\mid\ell_{t+1-{i^{\prime}}}(w)\geq b-j+1\}|\geq j+1

so $\mathcal{Q}({i^{\prime}}+1)$ holds.

We have proven that $\mathcal{Q}(i)$ holds, which means there is a set $S=\{v,w_{1},\dots,w_{i-1}\}$ of $i$ vertices such that $\ell_{t-i+1}(v)=b+1$ and, for any $1\leq j<i$ , we have $\ell_{t-i+1}(w_{j})\geq b+1-j$ . Also, for any vertex $w\notin S\cup\{u\}$ , we have $\ell_{t-i+1}(w)\geq 1$ . Finally, note that $\ell_{t-i+1}(w)=b+1$ for any vertex $w\in A_{t-i+1}$ , and $b+1$ is larger than $1$ and $b+1-j$ for any $1\leq j<i$ . Overall we obtain:

	$\displaystyle\Phi_{t-i+1}\geq\sum_{w\in S\cup\{u\}}\ell_{t-i+1}(w)+\sum_{w\in A% _{t-i+1}\setminus S\cup\{u\}}\ell_{t-i+1}(w)+\sum_{w\in V\setminus A_{t-i+1}% \cup S\cup\{u\}}\ell_{t-i+1}(w)$
	$\displaystyle\geq(\sum_{0\leq j<i}(b+1-j)+\|A_{t-i+1}\cap S\|)$
	$\displaystyle\nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ +2(\|A_{t-i+1}\|-\|A_{t-i+1}\cap S\|)+(n-i-1-\|A_{t-i+1}\|+\|A_{t-i+1}% \cap S\|)$
	$\displaystyle\geq((b-i)i+\binom{i+1}{2}+i)+\|A_{t-i+1}\|+n-i-1$
	$\displaystyle\geq(b-i)i+\binom{i+1}{2}+n-1+\|A_{t-i+1}\|$

This completes the proof. $\hfill\blacktriangleleft$

3.2 The General Case

Next, we provide the following theorem that extends the “Reachability Lemma”.

Theorem 3.4.

Let $\mathcal{G}$ be a temporal graph of lifetime $L$ , and $(u,v)$ be a pair of distinct vertices. If there is a set $T\subseteq[1,L-1]$ of time steps with $|T|\geq n-1$ , such that for every time step $t\in T$ , $u$ and $v$ are connected by a path, and the average length of these paths is $k$ , then there is a journey $u\rightsquigarrow_{b}v$ in $\mathcal{G}$ with $b=\left\lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+2$ .

Proof.

In this proof, we denote $d_{t}$ the length of the path connecting $u$ and $v$ at the time step $t\in T$ . For the purpose of contradiction, assume that there is no journey $u\rightsquigarrow_{b}v$ in $\mathcal{G}$ . In particular, this implies that $\ell_{L}(v)=b+1$ . So $\Phi_{L}\geq n-1+(|A_{L}|+1)b$ and $\Phi_{1}=(b+1)(n-1)$ , which means that $\Phi_{1}-\Phi_{L}\leq(n-2-|A_{L}|)b$ .

By Lemma 3.1,

\forall\,t\in T,\Phi_{t}-\Phi_{t+1}\geq b-d_{t}+1+|A_{t}|-|A_{t+1}|.

Also,

\forall\,t\notin T\cup\{L\},\Phi_{t}-\Phi_{t+1}\geq|A_{t}|-|A_{t+1}|.

We deduce from these inequalities that

	$\displaystyle\sum_{t\in T}(b-d_{t}+1+\|A_{t}\|-\|A_{t+1})\leq\sum_{t\in T}(\Phi_{% t}-\Phi_{t+1})$
	$\displaystyle=\Phi_{1}-\Phi_{L}-\sum_{t\notin T\cup\{L\}}(\Phi_{t}-\Phi_{t+1})% \leq(n-2-\|A_{L}\|)b-\sum_{t\notin T\cup\{L\}}(\|A_{t}\|-\|A_{t+1}\|).$

We deduce that

|T|(b-1)-\sum_{t\in T}(d_{t}-2)+\sum_{t\in[1,L-1]}(|A_{t}|-|A_{t+1}|)\leq(n-2-% |A_{L}|)b.

Since

\sum_{t\in[1,L-1]}(|A_{t}|-|A_{t+1}|)=|A_{1}|-|A_{L}|=n-2-|A_{L}|

, we have $|T|(b-1)\leq\sum_{t\in T}(d_{t}-2)+(n-2-|A_{L}|)(b-1)$ .
Using $|A_{L}|\geq 0$ , we obtain $(|T|-n+2)(b-1)\leq\sum_{t\in T}(d_{t}-2)$ and thus $b\leq\left\lfloor\frac{\sum_{t\in T}(d_{t}-2)}{|T|-n+2}\right\rfloor+1=\left% \lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+1$ , a contradiction. $\hfill\blacktriangleleft$

3.3 The case of paths of bounded length

In this section, we derive an upper bound on the number of paths $u\leftrightarrow_{k}v$ required to guarantee the existence of a journey $u\rightsquigarrow_{b}v$ in a temporal graph, where $b\geq k$ .

The following theorem gives back exactly the Reachability Lemma by setting $b=k=n-1$ . Moreover, it improves the bound presented by Balev et al. [6] in Lemma 7 because it states that $(k-1)(n-k)+1$ time steps with a path $u\leftrightarrow_{k}v$ ensures the existence of a journey $u\rightsquigarrow_{k}v$ .

Theorem 3.5.

Let $\mathcal{G}$ be a temporal graph on $n$ vertices, let $k$ and $b$ be integers that satisfy $1<k\leq b<n$ , and let $(u,v)$ be a pair of distinct vertices. If there are at least $\left\lfloor\frac{(n-k-1)(b-1)}{b-k+1}\right\rfloor+k$ snapshots with a path $u\leftrightarrow_{k}v$ , then there is a journey $u\rightsquigarrow_{b}v$ .

Proof.

It is sufficient to show the existence of the journey in the temporal graph obtained by removing the time steps with no paths $u\leftrightarrow_{k}v$ . So, for clarity and without loss of generality, we assume that there exists a path $u\leftrightarrow_{k}v$ at each time step. Also, for the purpose of contradiction, assume that there is an integer $t$ such that $\ell_{t}(v)=b+1$ and $t>\frac{(n-k-1)(b-1)}{b-k+1}+k$ . Note that $k\geq 2$ implies that $t>n-1$ . When $b=n-1$ , this is in contradiction with the Reachability Lemma which ensures the existence of a journey $u\rightsquigarrow_{(n-1,n)}v$ .

Therefore, we assume from now on that $b\leq n-2$ . It follows that

\frac{(n-k-1)(b-1)}{b-k+1}\geq\frac{(n-k-1)(b-1)}{n-2-k+1}=b-1\geq k-1,

which implies $t\geq 2k-2$ . In particular, it means that $t\geq k$ and $k\leq t-k+2$ . By Lemma 3.2, for every time step $k\leq t^{\prime}\leq t-k+1$ , we have $\Phi_{t^{\prime}}-\Phi_{t^{\prime}+1}\geq b-k+1+|A_{t^{\prime}}|-|A_{t^{\prime% }+1}|$ . Therefore,

\Phi_{k}-\Phi_{t-k+2}=(\Phi_{k}-\Phi_{k+1})+\dots+(\Phi_{t-k+1}-\Phi_{t-k+2})% \geq(t-2k+2)(b-k+1)+|A_{k}|-|A_{t-k+2}|.

Moreover, due to Lemma 3.1 for $i=k$ , we get $\Phi_{k}\leq(n-k)b+\binom{k}{2}+|A_{k}|+1$ since $t\geq k$ and thus $l_{k}(v)=b+1$ . Furthermore, by Lemma 3.3 for $i=k-1$ , we have

\Phi_{t-k+2}\geq(b-k+1)(k-1)+\binom{k}{2}+|A_{t-k+2}|+n-1

because $t\geq k$ and $\ell_{t}(v)=b+1$ . We deduce that

	$\displaystyle\Phi_{k}$	$\displaystyle-\Phi_{t-k+2}$
		$\displaystyle\leq(n-k)b+\binom{k}{2}+\|A_{k}\|+1-((b-k+1)(k-1)+\binom{k}{2}+\|A_{% t-k+2}\|+n-1)$
		$\displaystyle=(n-k-1)(b-1)+\|A_{k}\|-\|A_{t-k+2}\|-(b-k+1)(k-2)$

Therefore, we have

	$\displaystyle(n-k-1)(b-1)+\|A_{k}\|-\|A_{t-k+2}\|$	$\displaystyle-(b-k+1)(k-2)\geq\Phi_{k}-\Phi_{t-k+2}$
		$\displaystyle\geq(t-2k+2)(b-k+1)+\|A_{k}\|-\|A_{t-k+2}\|,$

and we deduce that $t\leq\frac{(n-k-1)(b-1)}{b-k+1}+k$ , a contradiction. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 3.6.

Note that both the upper bounds in the general case and in the restricted case are valid if the constraint that every edge is directed is added. Indeed, all the proofs in Section 3 are still valid if the paths connecting $u$ and $v$ have their edges directed from $u$ to $v$ .

4 Lower bounds for the sufficient conditions

In this section, we establish that the previously derived sufficient conditions for the existence of bounded-length journeys are essentially tight in the restricted case where all temporal paths have bounded length.

Let $k$ and $b$ be integers with $b\geq k$ . We construct a family of temporal graphs such that, at every time step, the vertices $u$ and $v$ are connected by a path of length exactly $k$ . We then characterize the maximum number of such time-distinct paths, denoted by $t_{f}$ , such that there is no journey $u\rightsquigarrow_{b}v$ .

We prove that, in this family of temporal graphs, the value of $t_{f}$ is asymptotically equal to the sufficient number of paths of length $k$ given in Theorem 3.5. Moreover, our bounds are tight whenever $n-k-1$ is a multiple of $b-k+1$ .

From this result, we derive a lower bound for the more general setting.

Theorem 4.1.

Let $k, b, n$ be integers satisfying $1<k\leq b<n$ . There exists a temporal graph $\mathcal{G}$ on $n$ vertices such that there is no journey $u\rightsquigarrow_{b}v$ but there are $\left\lfloor\frac{n-k-1}{\,b-k+1\,}\right\rfloor\cdot(b-1)\;+\;r\;+\;k-1$ time steps with a path $u\leftrightarrow_{k}v$ , where $r=(n-k-1\bmod(b-k+1))$ .

Proof.

Let $q=\left\lfloor\frac{n-k-1}{b-k+1}\right\rfloor$ and $t_{f}=(b-1)q+r+k-1$ . We construct the temporal graph $\mathcal{G}$ such that, at every time step in $[1,t_{f}]$ , the snapshot is a path of length $n-1$ as presented on Figure 2, and after this time step, the snapshots have no edges. For each time step $t\leq t_{f}$ , we denote by $s_{t}(w)$ the position of a vertex $w$ along this path, where position 0 corresponds to the extremity of the path that is closer to $u$ than to $v$ , and $n-1$ corresponds to the other extremity.

For every vertex $w$ and every time step $t$ such that $s_{t}(w)<n-1$ , we denote by $w_{t}$ the vertex satisfying $s_{t}(w_{t})=s_{t}(w)+1$ (i.e. $w_{t}$ is the neighbor of $w$ toward $v$ on the path at time step $t$ ).

Finally, for any time step $t>1$ , we say that a shift occurs at time $t$ if the following conditions hold:

		$\displaystyle s_{t}(u)=s_{t-1}(u_{t-1}),$
		$\displaystyle s_{t}(u_{t-1})=s_{t-1}(u),$
		$\displaystyle s_{t}(v)=s_{t-1}(v_{t-1}),$
		$\displaystyle s_{t}(v_{t-1})=s_{t-1}(v),$

and for all $w\in V\setminus\{u,v,u_{t-1},v_{t-1}\}$ , $s_{t}(w)=s_{t-1}(w)$ . A shift is illustrated in Figure 2 at time steps $k$ and $2k-1$ .

We now fully describe the temporal graph $\mathcal{G}$ . Initially, $G_{1}$ is the path $(u,u_{1},u_{2},\dots,u_{k-1},v$ , $v_{1},v_{2},\dots,v_{n-k-1}$ ). Until time $t_{f}$ , a snapshot is identical to the previous one, except at times $t+2$ where $t\mod(b-1)\in\{k-2,k-1,\dots,b-2\}$ . At these times, a shift occurs. From time $t_{f}+1$ on, the snapshots contain no edges. Note that $u$ and $v$ are at distance exactly $k$ at time $t$ for each $1\leq t\leq t_{f}$ .

The special case $b=k$ is depicted in Figure 2.

Figure 2: A representation of the first

3(k-1)

time steps in the constructed temporal graph for the case

b=k

(

b-k+1=1

so there is one shift every

k-1

time steps). Note that there is no journey of length

b

from

u

to

v

during these time steps.

In the remainder of the proof, we show that no journey $u\rightsquigarrow_{b}v$ exists by showing that $\ell_{t}(v)=b+1$ for all $t\geq 1$ .

It is tedious but straightforward to check that the local potentials evolve as follows.

Let $1\leq i,t\leq k-1$ . We have $\ell_{t}(u_{i})=i$ if $i<t$ , and $\ell_{t}(u_{i})=b+1$ otherwise. Also, $\ell_{t}(v)=b+1$ and $\ell_{t}(v_{j})=b+1$ for each $1\leq j\leq n-k-1$ .

Let us now consider $t>k-1$ , and let $q^{\prime}$ and $r^{\prime}$ be the non-negative integers such that $t=k+(b-1)q^{\prime}+r^{\prime}$ and $r^{\prime}<b-1$ . First, $\ell_{t}(w)=1$ for any $w$ such that $s_{t}(w)<s_{t}(u)$ . Similarly, $\ell_{t}(w)=b+1$ for any $w$ such that $s_{t}(w)\geq s_{t}(v)$ . Now, let $w_{1},\dots,w_{k-1}$ be the vertices inside the path from $u$ to $v$ at time $t$ . The sequence $\ell_{t}(w_{1}),\dots,\ell_{t}(w_{k-1})$ is as follows:

$\begin{cases}r^{\prime}+2,\dots,r^{\prime}+k-1,b+1&\textrm{ when }r^{\prime}% \leq b-k\\ 1,\dots,r^{\prime}-b+k,r^{\prime}+2,\dots,b&\textrm{ when }b-k<r^{\prime}<b-1% \end{cases}$

We now provide an informal description of how these values are obtained.

First, consider the case where $t=k+(b-1)q^{\prime}+r^{\prime}$ with $r^{\prime}\leq b-k$ . The values of the labels in this case can be shown to be as stated via induction on the time step. At time step $t$ , a shift occurs: the vertex $w_{0}$ , which was connected to $u$ in the path at time $t-1$ , satisfies $\ell_{t-1}(w_{0})=r^{\prime}+1$ and is no longer part of the path at time $t$ . Consequently, the only vertex in the path whose label changes at time $t$ is $w_{k-2}$ . Indeed, we have $\ell_{t-1}(w_{k-2})=b+1$ , while

$\ell_{t}(w_{k-2})=\ell_{t-1}(w_{k-3})+1=r^{\prime}+k-1.$

Next, consider the case where $t=k+(b-1)q^{\prime}+r^{\prime}$ with $r^{\prime}\in[b-k+1,b-2]$ . In this case, the path remains unchanged and the label values are updated in a way that propagates from the vertex $u$ , affecting one vertex per time step.

Therefore, at any time larger than $t_{f}$ , the local potential of $v$ is equal to $b+1$ , and thus there is no journey $u\rightsquigarrow_{b}v$ in $\mathcal{G}$ . $\hfill\blacktriangleleft$

In the following corollary of Theorem 4.1, we show that for any number $n$ of vertices, any integer $k\in[1,\sqrt{n/2}]$ , and any set of time steps $T$ with $|T|>4(n-2)$ , there exists a temporal graph with the following properties. There exists a pair of vertices $u$ and $v$ connected by a path at every time step in $T$ ; each such path has length exactly $k$ , and hence the average path length over $T$ is $k$ . Still, every shortest journey from $u$ to $v$ traverses at least $\left\lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+1$ edges.

This construction yields a lower bound for Theorem 3.4 in the case where the average path length satisfies $k\leq\sqrt{n/2}$ and the number of paths is greater than $4(n-2)$ .

Corollary 4.2.

Let $T$ be a set of time steps with $|T|>4(n-2)$ and $n>2$ , and let $k$ be an integer such that $k\leq\sqrt{n/2}$ . Then there exists a temporal graph $\mathcal{G}$ on $n$ vertices with the following properties. For every time step $t\in T$ , vertices $u$ and $v$ are connected by a path of length $k$ . Moreover, the shortest journey from $u$ to $v$ traverses at least $\left\lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+1$ edges.

Note that this statement also implies that the average path length is $k$ , too. Thus, this complements Theorem 3.4 for small values of $k$ .

Proof.

We construct a temporal graph $\mathcal{G}$ such that for every time step $t\in[1,|T|]$ the snapshot $G_{t}$ contains a path $u\leftrightarrow v$ of length exactly $k$ , and hence the average path length is $k$ . Let $b=\left\lfloor\frac{|T|(k-1)}{|T|-n+2}\right\rfloor-1.$ The proof has two steps. First, we show that $|T|<\left\lfloor\frac{n-k-1}{\,b-k+1\,}\right\rfloor(b-1)+k.$ Second, we deduce that there exists a temporal graph in which $u$ and $v$ are connected by a path of length $k$ at every time step of $T$ , while every journey from $u$ to $v$ has length strictly greater than $b$ . Consequently, the shortest journey from $u$ to $v$ traverses at least $b+1\geq\left\lfloor\frac{|T|}{|T|-n+2}(k-2)\right\rfloor+1$ edges.

We first prove that $\frac{b(k-1)+2n-2}{|T|-n+2}<1.$ Using the definition of $b$ ,

\frac{b(k-1)+2n-2}{|T|-n+2}<\frac{|T|}{|T|-n+2}\cdot\frac{(k-1)^{2}}{|T|-n+2}+% \frac{2n-2}{|T|-n+2}.

Since $k-1\leq\sqrt{(n-2)/2}$ and $|T|>4(n-2)$ , we have $|T|-n+2\geq 3(n-2)$ and thus $\frac{(k-1)^{2}}{|T|-n+2}\leq\frac{1}{6}.$

Hence, $\frac{b(k-1)+2n-2}{|T|-n+2}<\frac{|T|}{6(|T|-n+2)}+\frac{2n-2}{|T|-n+2}<1$ .

We next show that $(b-k+1)^{2}<n$ . From $|T|>4(n-2)$ we obtain $b<\frac{|T|}{|T|-n+2}(k-1)<\frac{4}{3}(k-1),$ and therefore $(b-k+1)^{2}<\left(\frac{k-1}{3}\right)^{2}<\frac{n}{36}<n,$ since $k-1<\sqrt{n/2}$ .

Finally, we compute $b=\left\lfloor\frac{|T|(k-1)}{|T|-n+2}\right\rfloor-1<\frac{|T|(k-1)}{|T|-n+2}% -\frac{b(k-1)+2n-2}{|T|-n+2}$ :

	$\displaystyle b<\frac{(\|T\|-b)(k-1)-2n+2}{\|T\|-n+2}$
	$\displaystyle\Rightarrow(\|T\|-n+2)b<(\|T\|-b)(k-1)-2n+2$
	$\displaystyle\Rightarrow(\|T\|-b)b+(b-n+2)b<(\|T\|-b)(k-1)-2n+2$
	$\displaystyle\Rightarrow(\|T\|-b)(b-k+1)<(n-b-3)(b-1)-n$
	$\displaystyle\Rightarrow(\|T\|-k)(b-k+1)-(b-k+1)^{2}<(n-b-3)(b-1)-n$
	$\displaystyle\Rightarrow(\|T\|-k)(b-k+1)<(n-b-3)(b-1)$
	$\displaystyle\Rightarrow\|T\|\leq\left\lfloor\frac{(n-b-3)}{b-k+1}(b-1)\right% \rfloor+k$
	$\displaystyle\Rightarrow\|T\|\leq\left\lfloor\frac{(n-k-2)-(b-k+1)}{b-k+1}(b-1)% \right\rfloor+k$
	$\displaystyle\Rightarrow\|T\|<\left\lfloor\frac{n-k-1}{b-k+1}\right\rfloor(b-1)+k$

By Theorem 4.1, for any integers $k$ , $b$ , and set of time steps $T$ satisfying $|T|\leq\left\lfloor\frac{n-k-1}{\,b-k+1\,}\right\rfloor(b-1)+k-1,$ there exists a temporal graph on $n$ vertices such that vertices $u$ and $v$ are connected by a path of length exactly $k$ at every time step of $T$ , while the shortest journey from $u$ to $v$ has length strictly greater than $b$ . Indeed, by construction there is no journey of length at most $b$ from $u$ to $v$ , yet by the Reachability Lemma a journey must exist since $u$ and $v$ are connected by a path at least $n-1$ times.

Consequently, for $|T|>4(n-2)$ and $k<\sqrt{n/2}$ , there exists a temporal graph on $n$ vertices in which $u$ and $v$ are connected by a path of length $k$ at every time step of $T$ , while the shortest journey from $u$ to $v$ traverses at least $b+1=\left\lfloor\frac{|T|}{|T|-n+2}(k-1)\right\rfloor\geq\left\lfloor\frac{|T|% }{|T|-n+2}(k-2)\right\rfloor+1$ edges. $\hfill\blacktriangleleft$

5 Applications

We focus on always connected temporal graphs, that is, temporal graphs where each snapshot is connected. This assumption allows us to transfer bounds on classical graph measures for every snapshot to corresponding temporal bounds in the temporal graph.

We consider temporal analogues of three standard static measures: the diameter, the average shortest-path length, and the closeness centrality. Each temporal measure is obtained by replacing, in the classical definition, the length of a shortest path with the length of a shortest journey in the temporal graph. We show that if a given measure is bounded by $k$ in every snapshot, then its temporal analogue approaches $k$ as the lifetime increases.

Throughout the section, we denote by $d_{j}(u,v)$ the length of a shortest journey from $u$ to $v$ in the temporal graph, and by $d_{p}(u,v,t)$ the length of a shortest path $u\leftrightarrow v$ in the snapshot at time $t$ . Since each snapshot is connected, we have for all $t>0$ and all $(u,v)\in V\times V$ , $d_{p}(u,v,t)\leq n-1.$

5.1 The temporal diameter

The definition of the temporal equivalent of the diameter in this section is

\max_{\{(u,v)\in V\times V\}}d_{j}(u,v)

Note that there exist multiple possible temporal equivalent to the definition of the diameter. For example, one of the definitions used in the literature defines the “temporal diameter” in a temporal graph as the maximum number of time steps for a journey between two vertices [26].

Lemma 5.1.

Let $\mathcal{G}$ be an always connected temporal graph of lifetime $L$ . If every snapshot has diameter at most $k$ and $L=(1+c)(n-1)$ with $c>0$ , then the temporal diameter of $\mathcal{G}$ is at most $(1+\frac{1}{c})\,k$ .

Proof.

By assumption, for every pair of vertices $(u,v)$ and every time step $t$ , the distance in snapshot $G_{t}$ satisfies $d_{p}(u,v,t)\leq k$ .

Since the graph is always connected, for every $(u,v)$ and every $t$ , there exists a path between $u$ and $v$ . We apply Theorem 3.4 with $T=[1,L-1]$ , which yields $d_{j}(u,v)\leq\frac{L}{L-n+1}\cdot\frac{1}{L}\sum_{t=1}^{L-1}d_{p}(u,v,t).$ .

Using $d_{p}(u,v,t)\leq k$ for all $t$ , we obtain $d_{j}(u,v)\leq\frac{L}{L-n+1}\cdot\frac{(L-1)k}{L}\leq\frac{L}{L-n+1}\,k.$

Since $L=(1+c)(n-1)$ , we have $L-n+1=c(n-1),$ and therefore $\frac{L}{L-n+1}=\frac{(1+c)(n-1)}{c(n-1)}=\frac{1+c}{c}.$ Hence, $d_{j}(u,v)\leq\frac{1+c}{c}\,k.$ As this bound holds for every pair of vertices, the temporal diameter of $\mathcal{G}$ is at most $\frac{1+c}{c}\,k$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark.

As a direct consequence of Lemma 5.1, if a temporal graph is always connected, each snapshot has diameter at most $k$ , and the lifetime satisfies $L=(1+c)(n-1)^{2}\text{ with }c>0,$ then the temporal graph admits an exploration, that is, a journey visiting all vertices, that traverses at most $(1+\frac{1}{c})\,k\,(n-1)$ edges.

5.2 The average shortest journey length

The definition of the temporal equivalent of the average shortest path length used in this section is

\frac{\sum_{(u,v)\in V\times V,u\neq v}d_{j}(u,v)}{n(n-1)}

We name it the average shortest journey length.

Lemma 5.2.

Let $\mathcal{G}$ be an always connected temporal graph of lifetime $L$ . If every snapshot has average shortest path length at most $k$ and $L=(1+c)(n-1)$ with $c>0$ , then the average shortest journey length of $\mathcal{G}$ is at most $(1+\frac{1}{c})\,k.$

Proof.

For any pair of distinct vertices $(u,v)$ , applying Theorem 3.4 with $T=[1,L-1]$ yields

d_{j}(u,v)\leq\sum_{t=1}^{L-1}\frac{d_{p}(u,v,t)}{L-n+1}.

Let $a$ denote the average shortest journey length: $a=\frac{1}{n(n-1)}\sum_{\begin{subarray}{c}u,v\in V\\ u\neq v\end{subarray}}d_{j}(u,v).$ Using the above bound, we obtain

a\leq\frac{1}{n(n-1)}\sum_{\begin{subarray}{c}u,v\in V\\ u\neq v\end{subarray}}\sum_{t=1}^{L-1}\frac{d_{p}(u,v,t)}{L-n+1}=\sum_{t=1}^{L% -1}\frac{1}{L-n+1}\cdot\frac{1}{n(n-1)}\sum_{\begin{subarray}{c}u,v\in V\\ u\neq v\end{subarray}}d_{p}(u,v,t).

By assumption, for every time step $t$ , $\frac{1}{n(n-1)}\sum_{u,v\in V,u\neq v}d_{p}(u,v,t)\leq k.$

Hence, $a\leq\frac{L-1}{L-n+1}\,k.$ Since $L=(1+c)(n-1)$ , we have $L-n+1=c(n-1)$ $a\leq\frac{1+c}{c}\,k$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark.

Observe that Lemma 5.2 generalizes Lemma 5.1 since, in any static graph, if the diameter is bounded by $k$ , then the average shortest-path length is also bounded by $k$ .

5.3 The temporal closeness centrality

In a static graph, the closeness centrality of a vertex quantifies how close, in terms of graph distance, the vertex is to all other vertices. It is defined as the inverse of the average shortest-path length from the vertex to all others (a formal definition is given in Section 2).

We define the temporal analogue of closeness centrality in a temporal graph $\mathcal{G}$ as follows. For a vertex $u\in V$ , its temporal closeness centrality is

C_{\mathcal{G}}(u)=\frac{n-1}{\sum_{v\in V}\max\{d_{j}(u,v),d_{j}(v,u)\}}\;,

where the maximum accounts for the fact that journeys in temporal graphs are directed.

Finally, we denote by $C_{t}(u)$ the closeness centrality of vertex $u$ in the snapshot at time step $t$ .

Lemma 5.3.

Let $\mathcal{G}$ be an always connected temporal graph of lifetime $L$ , and let $u$ be a vertex. If at every time step $t$ the closeness centrality of $u$ satisfies $C_{t}(u)\geq k$ and $L=(1+c)(n-1)\text{ with }c>0,$ then the temporal closeness centrality of $u$ satisfies $C_{\mathcal{G}}(u)\geq(1-\frac{1}{1+c})\,k.$

Proof.

By Theorem 3.4, applied with $T=[1,L-1]$ , for every vertex $v$ we have, $d_{j}(u,v)\leq\frac{L}{L-n+1}\cdot\frac{\sum_{t\in[1,L-1]}d_{p}(u,v,t)}{L}=% \sum_{t\in[1,L-1]}\frac{d_{p}(u,v,t)}{L-n+1}$ so

\max\{d_{j}(u,v),d_{j}(v,u)\}\leq\sum_{t\in[1,L-1]}\frac{d_{p}(u,v,t)}{L-n+1}.

We deduce that

C_{\mathcal{G}}(u)\geq\frac{n-1}{\sum_{v\in V}(\sum_{t\in[1,L-1]}\frac{d_{p}(u% ,v,t)}{L-n+1})}=\frac{(n-1)(L-n+1)}{\sum_{t\in[1,L-1]}(\sum_{v\in V}d_{p}(u,v,% t))}

And by assumption, for every time step $t$ , $\sum_{v\in V}d_{p}(u,v,t)\leq\frac{n-1}{k}$ , hence

C_{\mathcal{G}}(u)\geq\frac{(n-1)(L-n+1)}{\sum_{t\in[1,L-1]}\frac{n-1}{k}}=% \frac{(n-1)(L-n+1)}{(L-1)\frac{n-1}{k}}>\frac{L-n+1}{L}k=\frac{c}{1+c}k.\

$\hfill\blacktriangleleft$

6 Conclusion

The main theorem of this paper extends the well-known Reachability Lemma by establishing an upper bound on the number of edges traversed by a journey whose existence is guaranteed by that lemma. More precisely, it shows that, given two vertices connected by paths at distinct time steps, there exists a journey connecting these vertices whose length converges to the average length of the corresponding paths as the number of such paths increases.

This result admits of several applications. In particular, it applies to temporal graphs that are always connected, for which temporal analogues of classical topological and reachability measures are introduced.

A more restricted setting is also investigated, namely temporal graphs in which a pair of vertices is connected by paths at different time steps, each of length bounded by a fixed integer $k>0$ . Given an integer $b\geq k$ , nearly tight lower and upper bounds are established on the minimum number of such paths required to guarantee the existence of a journey of length $b$ connecting the two vertices. From the lower bound obtained in this restricted case, a corresponding lower bound for the main theorem is derived.

References

[1] Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:10, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SAND.2022.5.
[2] Eleni C Akrida, George B Mertzios, Paul G Spirakis, and Christoforos Raptopoulos. The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120:179–193, 2021. doi:10.1016/J.JCSS.2021.04.001.
[3] Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), volume 285 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2023.1.
[4] Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, LIPIcs, pages 149:1–149:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.149.
[5] Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, and Viktor Zamaraev. Temporal exploration of random spanning tree models. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 2876–2887. SIAM, 2026. doi:10.1137/1.9781611978971.106.
[6] 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), volume 330 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:5, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SAND.2025.18.
[7] Paul Bastide, Carla Groenland, Lukas Michel, and Clément Rambaud. Improved exploration of temporal graphs. CoRR, abs/2511.22604, 2025. doi:10.48550/arXiv.2511.22604.
[8] Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. Algorithmica, 85(3):688–716, 2023. doi:10.1007/S00453-022-01018-7.
[9] Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theor. Comput. Sci., 991:114434, 2024. doi:10.1016/J.TCS.2024.114434.
[10] 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. doi:10.1080/17445760.2012.668546.
[11] Siu-Wing Cheng. Shortest journeys in directed temporal graphs. International Journal of Foundations of Computer Science, 34(07):761–771, 2023. doi:10.1142/S0129054123420030.
[12] Umesh Sandeep Danda, G Ramakrishna, Jens M Schmidt, and Mithinti Srikanth. On short fastest paths in temporal graphs. In International Workshop on Algorithms and Computation, pages 40–51. Springer, 2021. doi:10.1007/978-3-030-68211-8_4.
[13] Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:18, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.55.
[14] Jessica A. Enright, Kitty Meeks, and Hendrik Molter. Counting temporal paths. Algorithmica, 87(5):736–782, 2025. doi:10.1007/S00453-025-01301-3.
[15] Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1–18, 2021. doi:10.1016/J.JCSS.2021.01.005.
[16] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, July 2019. doi:10.4230/LIPIcs.ICALP.2019.141.
[17] Thomas Erlebach and Jakob T Spooner. Exploration of k-edge-deficient temporal graphs. Acta Informatica, 59(4):387–407, 2022. doi:10.1007/S00236-022-00421-5.
[18] Thomas Erlebach and Jakob T Spooner. Parameterised temporal exploration problems. Journal of Computer and System Sciences, 135:73–88, 2023. doi:10.1016/J.JCSS.2023.01.003.
[19] Paola Flocchini, Bernard Mans, and Nicola Santoro. Exploration of periodically varying graphs. In International Symposium on Algorithms and Computation, pages 534–543. Springer, 2009. doi:10.1007/978-3-642-10631-6_55.
[20] David Ilcinkas and Ahmed M Wade. Exploration of the t-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems, 62(5):1144–1160, 2018. doi:10.1007/S00224-017-9796-3.
[21] David Ilcinkas and Ahmed M Wade. Exploration of dynamic cactuses with sub-logarithmic overhead. Theory of Computing Systems, 65(2):257–273, 2021. doi:10.1007/S00224-020-10001-0.
[22] David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 504–513, 2000. doi:10.1145/335305.335364.
[23] Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 513–522, 2010. doi:10.1145/1806689.1806760.
[24] Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner enumeration for temporal graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025), pages 9–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SAND.2025.9.
[25] Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239–280, 2016. doi:10.1080/15427951.2016.1177801.
[26] Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1–23, 2016. doi:10.1016/J.TCS.2016.04.006.
[27] Lutz Oettershagen and Petra Mutzel. Computing top-k temporal closeness in temporal networks. Knowl. Inf. Syst., 64(2):507–535, 2022. doi:10.1007/S10115-021-01639-4.
[28] Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs. Proceedings of the VLDB Endowment, 7(9):721–732, 2014. doi:10.14778/2732939.2732945.
[29] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11):2927–2942, 2016. doi:10.1109/TKDE.2016.2594065.
[30] B Bui Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(02):267–285, 2003. doi:10.1142/S0129054103001728.

[bib.bib1] [1] Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:10, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SAND.2022.5.

[bib.bib2] [2] Eleni C Akrida, George B Mertzios, Paul G Spirakis, and Christoforos Raptopoulos. The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120:179–193, 2021. doi:10.1016/J.JCSS.2021.04.001.

[bib.bib3] [3] Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), volume 285 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2023.1.

[bib.bib4] [4] Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, LIPIcs, pages 149:1–149:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.149.

[bib.bib5] [5] Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, and Viktor Zamaraev. Temporal exploration of random spanning tree models. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 2876–2887. SIAM, 2026. doi:10.1137/1.9781611978971.106.

[bib.bib6] [6] 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), volume 330 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:5, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SAND.2025.18.

[bib.bib7] [7] Paul Bastide, Carla Groenland, Lukas Michel, and Clément Rambaud. Improved exploration of temporal graphs. CoRR, abs/2511.22604, 2025. doi:10.48550/arXiv.2511.22604.

[bib.bib8] [8] Benjamin Merlin Bumpus and Kitty Meeks. Edge exploration of temporal graphs. Algorithmica, 85(3):688–716, 2023. doi:10.1007/S00453-022-01018-7.

[bib.bib9] [9] Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theor. Comput. Sci., 991:114434, 2024. doi:10.1016/J.TCS.2024.114434.

[bib.bib10] [10] 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. doi:10.1080/17445760.2012.668546.

[bib.bib11] [11] Siu-Wing Cheng. Shortest journeys in directed temporal graphs. International Journal of Foundations of Computer Science, 34(07):761–771, 2023. doi:10.1142/S0129054123420030.

[bib.bib12] [12] Umesh Sandeep Danda, G Ramakrishna, Jens M Schmidt, and Mithinti Srikanth. On short fastest paths in temporal graphs. In International Workshop on Algorithms and Computation, pages 40–51. Springer, 2021. doi:10.1007/978-3-030-68211-8_4.

[bib.bib13] [13] Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:18, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.55.

[bib.bib14] [14] Jessica A. Enright, Kitty Meeks, and Hendrik Molter. Counting temporal paths. Algorithmica, 87(5):736–782, 2025. doi:10.1007/S00453-025-01301-3.

[bib.bib15] [15] Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1–18, 2021. doi:10.1016/J.JCSS.2021.01.005.

[bib.bib16] [16] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, July 2019. doi:10.4230/LIPIcs.ICALP.2019.141.

[bib.bib17] [17] Thomas Erlebach and Jakob T Spooner. Exploration of k-edge-deficient temporal graphs. Acta Informatica, 59(4):387–407, 2022. doi:10.1007/S00236-022-00421-5.

[bib.bib18] [18] Thomas Erlebach and Jakob T Spooner. Parameterised temporal exploration problems. Journal of Computer and System Sciences, 135:73–88, 2023. doi:10.1016/J.JCSS.2023.01.003.

[bib.bib19] [19] Paola Flocchini, Bernard Mans, and Nicola Santoro. Exploration of periodically varying graphs. In International Symposium on Algorithms and Computation, pages 534–543. Springer, 2009. doi:10.1007/978-3-642-10631-6_55.

[bib.bib20] [20] David Ilcinkas and Ahmed M Wade. Exploration of the t-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems, 62(5):1144–1160, 2018. doi:10.1007/S00224-017-9796-3.

[bib.bib21] [21] David Ilcinkas and Ahmed M Wade. Exploration of dynamic cactuses with sub-logarithmic overhead. Theory of Computing Systems, 65(2):257–273, 2021. doi:10.1007/S00224-020-10001-0.

[bib.bib22] [22] David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 504–513, 2000. doi:10.1145/335305.335364.

[bib.bib23] [23] Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 513–522, 2010. doi:10.1145/1806689.1806760.

[bib.bib24] [24] Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner enumeration for temporal graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025), pages 9–1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SAND.2025.9.

[bib.bib25] [25] Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239–280, 2016. doi:10.1080/15427951.2016.1177801.

[bib.bib26] [26] Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1–23, 2016. doi:10.1016/J.TCS.2016.04.006.

[bib.bib27] [27] Lutz Oettershagen and Petra Mutzel. Computing top-k temporal closeness in temporal networks. Knowl. Inf. Syst., 64(2):507–535, 2022. doi:10.1007/S10115-021-01639-4.

[bib.bib28] [28] Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs. Proceedings of the VLDB Endowment, 7(9):721–732, 2014. doi:10.14778/2732939.2732945.

[bib.bib29] [29] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11):2927–2942, 2016. doi:10.1109/TKDE.2016.2594065.

[bib.bib30] [30] B Bui Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(02):267–285, 2003. doi:10.1142/S0129054103001728.

	$\displaystyle\Phi_{t}-\Phi_{t+1}$	$\displaystyle\geq\sum_{i\in I}\ell_{t}(w_{i})-\sum_{i\in I}\ell_{t+1}(w_{i})+% \sum_{w\notin\{w_{i}\mid i\in I\}}(\ell_{t}(w)-\ell_{t+1}(w))$
		$\displaystyle\geq b+1-\|I\|+\|A_{t}\setminus(A_{t+1}\cup\{w_{f},\dots,w_{d_{t}-1}% \})\|$
		$\displaystyle\geq b+1-d_{t}+\|A_{t}\cap\{w_{f},\dots,w_{d_{t}-1}\}\|+\|A_{t}% \setminus(A_{t+1}\cup\{w_{f},\dots,w_{d_{t}-1}\})\|$
		$\displaystyle\geq b-d_{t}+1+\|A_{t}\|-\|A_{t+1}\|.$

	$\displaystyle\Phi_{t-i+1}\geq\sum_{w\in S\cup\{u\}}\ell_{t-i+1}(w)+\sum_{w\in A% _{t-i+1}\setminus S\cup\{u\}}\ell_{t-i+1}(w)+\sum_{w\in V\setminus A_{t-i+1}% \cup S\cup\{u\}}\ell_{t-i+1}(w)$
	$\displaystyle\geq(\sum_{0\leq j<i}(b+1-j)+\|A_{t-i+1}\cap S\|)$
	$\displaystyle\nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ +2(\|A_{t-i+1}\|-\|A_{t-i+1}\cap S\|)+(n-i-1-\|A_{t-i+1}\|+\|A_{t-i+1}% \cap S\|)$
	$\displaystyle\geq((b-i)i+\binom{i+1}{2}+i)+\|A_{t-i+1}\|+n-i-1$
	$\displaystyle\geq(b-i)i+\binom{i+1}{2}+n-1+\|A_{t-i+1}\|$

	$\displaystyle b<\frac{(\|T\|-b)(k-1)-2n+2}{\|T\|-n+2}$
	$\displaystyle\Rightarrow(\|T\|-n+2)b<(\|T\|-b)(k-1)-2n+2$
	$\displaystyle\Rightarrow(\|T\|-b)b+(b-n+2)b<(\|T\|-b)(k-1)-2n+2$
	$\displaystyle\Rightarrow(\|T\|-b)(b-k+1)<(n-b-3)(b-1)-n$
	$\displaystyle\Rightarrow(\|T\|-k)(b-k+1)-(b-k+1)^{2}<(n-b-3)(b-1)-n$
	$\displaystyle\Rightarrow(\|T\|-k)(b-k+1)<(n-b-3)(b-1)$
	$\displaystyle\Rightarrow\|T\|\leq\left\lfloor\frac{(n-b-3)}{b-k+1}(b-1)\right% \rfloor+k$
	$\displaystyle\Rightarrow\|T\|\leq\left\lfloor\frac{(n-k-2)-(b-k+1)}{b-k+1}(b-1)% \right\rfloor+k$
	$\displaystyle\Rightarrow\|T\|<\left\lfloor\frac{n-k-1}{b-k+1}\right\rfloor(b-1)+k$

On Sufficient Conditions for Short Journeys in Temporal Graphs

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our results.

2 Preliminaries

Definition 2.1 (Temporal graph).

Definition 2.2 (Path).

Definition 2.3 (Strict Journey).

Lemma 2.4 (Reachability Lemma [15]).

Definition 2.5 (Closeness centrality (in static graphs)).

3 The sufficient conditions for short journeys

3.1 Technical Tools

Lemma 3.1.

Proof.

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

3.2 The General Case

Theorem 3.4.

Proof.

3.3 The case of paths of bounded length

Theorem 3.5.

Proof.

▶ Remark 3.6.

4 Lower bounds for the sufficient conditions

Theorem 4.1.

Proof.

Corollary 4.2.

Proof.

5 Applications

5.1 The temporal diameter

Lemma 5.1.

Proof.

▶ Remark.

5.2 The average shortest journey length

Lemma 5.2.

Proof.

▶ Remark.

5.3 The temporal closeness centrality

Lemma 5.3.

Proof.

6 Conclusion

References

$\blacktriangleright$ Remark 3.6.

$\blacktriangleright$ Remark.

$\blacktriangleright$ Remark.