# On the Complexity of Computing a Fastest Temporal Path in Interval Temporal Graphs*

Guillaume Aubian¹, Filippo Brunelli², Feodor Dragan³, Guillaume Ducoffe⁴,
Michel Habib¹, Allen Ibiapina¹, and Laurent Viennot⁵

¹IRIF, CNRS & Université Paris Cité

²European Commission — Joint Research Centre (JRC)

³Kent State University

⁴University of Bucharest, Faculty of Mathematics and Computer Science, and National Institute for Research and Development in Informatics, Romania

⁵Inria, DI ENS, Paris

January 17, 2025

## Abstract

Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal aspects of the interactions: time of appearance, duration, delay of transmission. In the point model, edges appear at specific points in time, while in the more general interval model, edges can be present over multiple time intervals. In both models, the delay for traversing an edge can change with each edge appearance. When time is discrete, the two models are equivalent in the sense that the presence of an edge during an interval is equivalent to a sequence of point-in-time occurrences of the edge. However, this transformation can drastically change the size of the input and has complexity issues. Indeed, we show a gap between the two models with respect to the complexity of the classical problem of computing a fastest temporal path from a source vertex to a target vertex, i.e. a path where edges can be traversed one after another in time and such that the total duration from source to target is minimized. It can be solved in near-linear time in the point model, while we show that the interval model requires quadratic time under classical assumptions of fine-grained complexity. With respect to linear time, our lower bound implies a factor of the number of vertices, while the best known algorithm has a factor of the number of underlying edges. We show a similar gap for computing a shortest temporal path, i.e. with minimum number edges. Interestingly, we show that near-linear time for fastest temporal path is possible in the interval model when restricted to all delays being zero, i.e. traversing an edge is instantaneous.

**Keywords:** Temporal graphs, Dynamic networks, Time-dependent networks, Fastest temporal path, Shortest temporal path, Fine-grained complexity

## 1 Introduction

Graphs are the standard mathematical framework for representing relationships within networks. However, in many real-world scenarios, such as transportation systems or social networks, these relationships are time-sensitive and evolve over time. Temporal graphs address this dynamic nature by modeling networks where connections change over time. Their study traces back to

<footnote>*This work was supported by the French National Research Agency (ANR) through project Tempogral with reference number ANR-22-CE48-0001.</footnote>
<table><caption>Table 1: State of the art on the complexity of computing a fastest temporal path in a temporal graph with *n* vertices and *M* edge appearances. We let *m* denote the number of underlying edges, i.e. the number of distinct vertex pairs connected at some time. We assume $n \le m \le M$ without loss of generality as isolated vertices can easily be handled.</caption><thead><tr><th></th><th>positive delays</th><th>non-negative delays</th></tr></thead><tbody><tr><td>point temporal graph</td><td>Q&#771;(M) [9, 10] and [25, 26]</td><td>Q&#771;(M) [2]</td></tr><tr><td>interval temporal graph</td><td colspan="2">Q&#771;(mM) = Q&#771;(M<sup>2</sup>) [8]</td></tr></tbody></table>

time-dependent networks [7] in the context of road networks. They were later re-introduced under various flavors of models, see e.g. [5, 16, 22, 19]. In the simplest model, each edge appears at specific points in time. In the most advanced model, each edge is present during full time intervals, and the delay for traversing it is given by a time-dependent function which is often assumed to be piece-wise linear (and linear in each interval of appearance without loss of generality). We are interested in highlighting the difference in complexity between these two models, which we will call *point* temporal graph and *interval* temporal graph, respectively.

Note that the interval model obviously encompasses the point model, since a point in time corresponds to a time interval with equal bounds. In both models, each appearance of an edge can be represented by a tuple storing the two vertices of the edge with the few associated time parameters (assuming linearity in each appearance interval for the interval model), and the size of the input can be measured by the total number *M* of such edge appearances. If we remove the time information from the list of tuples describing a temporal graph and forget the multiplicities, we obtain what we call its underlying graph. If time is discrete, the two models may seem equivalent, since an edge appearance during an interval of length *l* can be seen as *l* point-by-point appearances (with a specific delay for each point). However, the size of the input can then grow by an exponential factor, leading to incomparable complexity in solving a problem in one model or the other.

A recent strand of research revisits all classical graph problems in the context of temporal graphs, see e.g. [18, 23, 6, 13, 21]. Most of these works focus on the point model while the interval model may have been overlooked. Interestingly, the natural notion of connectivity in temporal graphs arises from temporal paths whose computation is the subject of various works in both models (see e.g. [4, 26]). A temporal path is a path whose edges can be traversed one after another sequentially in time. Surprisingly, it appears that the complexity of the basic problem of computing a temporal path with minimum duration is not completely settled yet.

More precisely, when considering all temporal paths between a source vertex and a target vertex, the time aspect gives rise to several notions of shortest path: in particular, a *foremost* temporal path arrives at the target as early as possible, a *shortest* temporal path uses a minimum number of edges, and a *fastest* temporal path has a minimum duration, i.e. the time span between leaving the source and arriving at the target is minimal. In the interval model, the problem of finding a foremost temporal path can be solved in near-linear time [11, 4], while the best algorithms for computing a shortest temporal path [4, 17] or a fastest temporal path [8] are slower by a factor depending on the size of the underlying graph, respectively *n* and *m* if the underlying graph has *n* vertices and *m* edges. In the point model, the three problems can be solved in near-linear time [26], even when waiting restrictions are imposed [2]. As we mostly focus on fastest temporal path computation, Table 1 gives a summary of the best known algorithms. To the best of our knowledge, no non-trivial lower bounds are known. Thus, we ask whether a slowdown factor proportional to the size of the underlying graph in the interval model is necessary to compute a fastest temporal path?

**Our contribution** First, we give strong elements towards a positive answer to the above question. More precisely, we provide a subcubic reduction from negative triangle detection to fastest
temporal path computation. The former consists in detecting whether a weighted graph has a triangle of negative total edge weight. This reduction implies that, for any $\epsilon > 0$, an $O((nM)^{1-\epsilon})$-time algorithm for fastest temporal path in interval temporal graphs with $n$ vertices and $M$ edge appearances would break the state of the art for several classical problems, including e.g. all pair shortest path (APSP), the replacement paths problem on weighted directed graphs, verifying the correctness of a matrix product over the $(\min, +)$-semiring among others [24]. Our reduction is restricted to undirected interval temporal graphs with constant delays, i.e. each edge can be traversed in both directions with symmetric constant delay in each time interval in which it appears.

Second, we provide a deterministic combinatorial near-linear-time algorithm for finding a fastest temporal path in undirected interval temporal graphs with uniform delay zero, i.e., the delay for traversing an edge is always zero. This restricted setting is particularly interesting as it is classically used to model social interactions [16, 19]. Although it is quite natural to use dynamic computation of connected components for computing fastest temporal paths, we have a stronger result since our algorithm solves the profile problem which consists in computing, given a source vertex and a target vertex, a representation of the (profile) function that assigns to each possible departure time from the source, the corresponding earliest arrival time at the target. Note that the duration of a fastest temporal path can be inferred from the profile function.

Third, we show that this restricted setting to undirected temporal graphs with uniform zero delay is the widest possible in which we can expect a near-linear time combinatorial algorithm by providing two other similar lower bounds based on the conjecture that there is no $O(n^{3-\epsilon})$-time combinatorial algorithm for finding a triangle in an undirected graph. More precisely, we provide one lower bound in undirected interval graphs with uniform delay one, and the other in directed interval graphs with uniform delay zero. Note that triangle detection is a classical problem in fine-grained complexity which is, for example, subcubic equivalent to combinatorial Boolean matrix multiplication [24].

See Table 2 for a summary of our results concerning fastest temporal paths. In addition, we prove a similar lower bound of $\Omega((nM)^{1-\epsilon})$ time for computing a shortest path based on the same conjecture that there is no $O(n^{3-\epsilon})$-time combinatorial algorithm for finding a triangle in an undirected graph. Although the reduction we provide has a similar flavor of the previous ones, it constructs a graph of linear diameter rather than constant. This is indeed necessary as the algorithm of [4] finds a shortest temporal path in $\tilde{O}(Dm)$ where $D \le n$ is the largest length of a temporal path (in terms of number of edges) and $m$ is the size of the underlying graph. Note that it uses a sorted data structure which can be pre-computed in $\tilde{O}(M)$ time. Here, our reduction holds within undirected temporal graphs with uniform delay zero, and we do not expect a faster algorithm in that case.

**Related work** The difference in complexity between the interval model and the point model has already been noticed in [3] where the authors consider the profile problem and solve a generalization of it in the point model. Profile computation cannot be performed in polynomial time if the delay for traversing an edge is represented by a polyline [12]. However, it can be done in quadratic time

<table><caption>Table 2: Summary of our results on the complexity of computing a fastest temporal path in an interval temporal graph with $n$ vertices and $M$ edge appearances. The lower-bounds are given for any $\epsilon > 0$. Those marked with a * correspond to a sub-cubic reduction from negative triangle detection, while those marked with a + correspond to a sub-cubic reduction from triangle detection and concern combinatorial algorithms.</caption><thead><tr><th></th><th>non-negative delays</th><th>uniform delay one</th><th>uniform zero delay</th></tr></thead><tbody><tr><th>undirected</th><td>$\Omega((nM)^{1-\epsilon})^*$ Th. 1</td><td>$\Omega((nM)^{1-\epsilon})^+$ Th. 2</td><td>$\tilde{O}(M)$ Th. 4</td></tr><tr><th>directed</th><td></td><td></td><td>$\Omega((nM)^{1-\epsilon})^+$ Th. 3</td></tr></tbody></table>
in the interval model with constant delays [8], and in near-linear time in the point model [10].

**Structure of the paper** After formally introducing temporal graphs, we first show our lower bounds based on reductions from classical problems of fine-grained complexity in *P*. We then present an algorithm that escapes these bounds by restricting the input to zero delays.

## 2 Preliminaries

We represent times with integers for the sake of simplicity and use greek letters to name times. An interval of time [$\tau_1, \tau_2$] with $\tau_1 \le \tau_2$ represents all times $\tau$ satisfying $\tau_1 \le \tau \le \tau_2$. For $\tau_1 < \tau_2$, we similarly define $(\tau_1, \tau_2]$ [$[\tau_1, \tau_2)$ respectively) as the set of times $\tau$ satisfying $\tau_1 < \tau \le \tau_2$ $(\tau_1 \le \tau < \tau_2$ respectively).

An interval temporal graph, hereafter referred to simply as a temporal graph, is a pair $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of temporal edges. Each temporal edge is a quintuple $e = (u, v, \tau_1, \tau_2, \delta)$, where $u$ and $v$ are vertices, $\tau_1, \tau_2$ and $\delta$ are integers with $\tau_1 \le \tau_2$ and $\delta \ge 0$ that represent its starting time, its ending time and its delay (or traveling time) respectively. Such a temporal edge represents the presence of edge $uv$ during [$\tau_1, \tau_2$], that is, it can be traversed starting from its tail $u$ at any time $\tau \in [\tau_1, \tau_2]$ to arrive in its head $v$ at time $\tau + \delta$. We say that $e$ connects $uv$ during interval $[\tau_1, \tau_2]$ with delay $\delta$. We let tail($e$) = $u$, head($e$) = $v$, start($e$) = $\tau_1$, end($e$) = $\tau_2$, and delay($e$) = $\delta$ denote its tail, its head, its starting time, its ending time, and its delay respectively. We mostly consider undirected temporal graphs where edges can be traversed in both direction. In that case, it is assumed that $E$ is symmetric: for each $(u, v, \tau_1, \tau_2, \delta) \in E$, the symmetrical temporal edge $(v, u, \tau_1, \tau_2, \delta)$ is also in $E$. In other words, $G$ is said to be undirected when $E$ is symmetric.

The underlying graph of $G$ is the (static) graph $G' = (V, E')$ with same vertex set $V$ and edge set $E' = \{uv : \exists(u, v, \tau_1, \tau_2, \delta) \in E\}$. Note that we let $uv$ denote the directed edge from $u$ to $v$. We say that an edge $uv$ of the underlying graph is present during [$\tau_1, \tau_2$] with delay $\delta$ when there is a temporal edge $(u, v, \tau_1, \tau_2, \delta)$ in $E$. When the temporal graph is undirected we also assume that the symmetrical edge is in $E$. When $\tau_1 = \tau_2$, we say that $uv$ is present at point $\tau_1$ with delay $\delta$. When a temporal graph is clear from the context, we let $n = |V|$ denote its number of vertices, $M = |E|$ denote its number of temporal edges, and $m = |E'|$ denote its number of underlying edges. It should be noticed that $M$ can be much larger than $m$, since an edge in $E'$ may correspond to many temporal edges in $E$. For the sake of simplicity, we assume that any vertex appears at least in one temporal edge so that we have $n = O(m)$.

A temporal walk in $G$ is a sequence of pairs $Q = (e_1, \tau_1), \dots, (e_k, \tau_k)$ where, for each $i \in [k] = \{1, \dots, k\}$, $e_i \in E$ is a temporal edge and $\tau_i$ is a traversal time in the presence interval of $e_i$, i.e. satisfying $start(e_i) \le \tau_i \le end(e_i)$. It is also required that $head(e_i) = tail(e_{i+1})$ for all $i \in [k-1]$, in other words it induces a walk in the underlying graph $G'$, and that $\tau_i + delay(e_i) \le \tau_{i+1}$ for all $i \in [k-1]$, that is each temporal edge is traversed one after the other in time. When $s = tail(e_1)$ and $head(e_k) = t$, we say that $Q$ is a temporal st-walk. We also says that $Q$ is a temporal walk departing from $s$ at time $\tau_1$ and arriving in $t$ at time $\tau_k + \delta_k$. We let $dep(Q) = \tau_1$, $arr(Q) = \tau_k + \delta_k$ and $len(Q) = k$ denote its departure time, its arrival time and its length in number of edges respectively. Its duration is defined as $dur(Q) = arr(Q) - dep(Q) = \tau_k + \delta_k - \tau_1$. $Q$ is pairwise distinct, $Q$ is said to be a temporal path, or a temporal st-path if $s = tail(e_1)$ and $head(e_k) = t$. Note that any temporal st-walk with $s \neq t$ can be transformed into a temporal st-path by removing sequences of temporal edges forming loops. A fastest temporal st-path is defined as a temporal st-path with minimum duration. A shortest temporal st-path is defined as a temporal st-path with minimum length.
3 Lower bounds for fastest temporal path

**Theorem 1.** *Assuming the APSP Conjecture, for any ε > 0, there is no O((nM)1−ε)-time algorithm for computing a fastest temporal path in a temporal graph, even if the temporal graph is undirected.*

Proof. The NEGATIVE TRIANGLE DETECTION problem asks for the existence in an edge-weighted
graph of a triangle whose total weight is negative. Assuming the APSP Conjecture, for any ε > 0,
there is no O(n³⁻³⁻¹)-time algorithm for this problem [24]. So in what follows, in order to prove the
theorem, we present an O(n + m)-time reduction from NEGATIVE TRIANGLE DETECTION to the
problem of computing a fastest temporal path in a temporal graph. For that, let G = (V, E, w) be
an arbitrary undirected edge-weighted graph with n nodes and m edges where w : E → Z assigns
a weight w<sub>e</sub> to each edge e ∈ E. Without loss of generality, V = {0, 1, 2, ..., n − 1} and G is
loopless. Let T = 2n max<sub>e∈E</sub> |w<sub>e</sub>|. We construct from G an undirected temporal graph H<sub>G</sub> as
follows:

* The vertex set is {$s, t$} $\cup V_1$ $\cup V_2$ $\cup V_3$ where $V_1, V_2, V_3$ are disjoint copies of $V$ and $s, t$ are two additional vertices. For every $v \in V$, let $v_1 \in V_1$, $v_2 \in V_2$, $v_3 \in V_3$ denote its copies. $V_1, V_2, V_3$ are independent sets.

* The underlying edge set includes {$sv_1, v_3t : v \in V$} $\cup \{u_1v_2, u_2v_3 : uv \in E\}$ (and symmetrical edges).

* For every $uv \in E$, edges $u_1v_2, u_2v_3$ are present during $[0, 2mT]$ with delay $T/2 + w_{uv}$.

* Finally, let $E = \{e_1, e_2, \dots, e_m\}$ be an enumeration of the edge set $E$. For each $i \in [m]$, let $u$ and $v$ be the endpoints of $e_i$ such that $u < v$. Then, edge $su_1$ is present at point $2(i-1)T$ with delay $(T + w_{e_i})/2$ and edge $v_3t$ is present during $[2(i-1)T, 2iT]$ with same delay $(T + w_{e_i})/2$.

<figure><img src="image_1.png" /><figcaption>Figure 1: A schematic view of the reduction from Negative Triangle Detection to Fastest Temporal Path.</figcaption></figure>

We have $M = 8m$ (counting also symmetrical temporal edges) and the construction takes
linear time. Figure 1 shows a schematic view of the resulting temporal graph.

We claim that there is a temporal st-path in $H_G$ with duration less than $2T$ if and only if $G$
contains a negative triangle. For that, let us fix a temporal st-path $P$ of minimum duration. By
the construction of $H_G$, its first temporal edge is present at time $2(i-1)T$ for some $i \in [m]$. Let $uv$ be the endpoints of $e_i$ so that $P$ starts with edge $su_1$. If the duration of $P$ is less than $2T$, then $P$ ends with the only edge with head $t$ appearing in $[2(i-1)T, 2iT)$, that is edge $v_3t$. Let $k < n$ be the number of edges of $P$. The duration of $P$ must be at least $k(T/2 - \max_{e \in E} |w_e|) > (k/2 - 1)T$ while it less than $2T$. So, we assume $k \le 5$ in what follows. Furthermore, since by construction $H_G$ is bipartite (with respective partite sets $\{s, t\} \cup V_2$ and $V_1 \cup V_3$), we must have $k = 4$. In this situation, there must exist a vertex $x$ such that $uvx$ is a triangle of $G$ and the underlying edges of $P$ are $su_1, u_1x_2, x_2v_3, v_3t$. As the temporal edges connecting $su_1$ and $v_3t$ have same delay $(T + w_{e_i})/2$, the duration of $P$ is at least $2T + w_{e_i} + w_{ux} + w_{xv}$, which is less than $2T$ if and only if the triangle $uvx$ is negative. Conversely, if $uvx$ is a negative triangle, then up to reordering we can assume that its edges are $e_1, e_2, e_3$. Then, there exists a temporal $(s, t)$-tpath that starts at time 0, has no waiting time, and has duration less than $2T$. Therefore, the claim is proved. $\square$

**Remark.** The known reduction to negative triangle detection usually requires weights in the range $\{-n^c, \dots, n^c\}$ for some large enough integer $c$ [24]. It yields an $\Omega(nm^{1-\epsilon})$ bound for APSP in the regime $m = \Theta(n^2)$. Note that a similar bound of $\Omega(nm^{1-\epsilon})$ is also conjectured to hold in the sparse regime $m = \Theta(n^{1+1/\ell})$ for any integer $\ell > 0$ [20].

The following hardness result is inspired from that of Theorem 1, but it requires some adjustments (and a different complexity hypothesis) in order to cope with uniform delay one.

**Theorem 2.** If, for every $\varepsilon > 0$, there is no combinatorial $O(n^{3-\varepsilon})$-time algorithm for detecting a triangle in a graph, then for every $\varepsilon' > 0$, there is no combinatorial $O((nM)^{1-\varepsilon'})$-time algorithm for computing a fastest temporal path in a temporal graph, even if the temporal graph is undirected and all temporal edges have delay one.

*Proof.* Let $G = (V, E)$ be an arbitrary unweighted graph. Without loss of generality, $V = \{0, 1, 2, \dots, n-1\}$ and $G$ is loopless. Let $N$ be some large enough constant (say, $N = 10$). The undirected temporal graph $H_G$ is constructed from $G$ as follows:

* The vertex set is $\{s, t\} \cup V_1 \cup V_2 \cup V_3$ where $V_1, V_2, V_3$ are disjoint copies of $V$. For every $v \in V$, let $v_1 \in V_1, v_2 \in V_2, v_3 \in V_3$ denote its copies.

* The underlying edge set includes $\{sv_1, v_3t : v \in V\} \cup \{u_1v_2, u_2v_3 : uv \in E\}$ (and symmetrical edges).

* For every $uv \in E$, edges $u_1v_2, u_2v_3$ are present during $[0, n \times N + 3]$.

* For every $v \in V$, the edge $sv_1$ is present at point $v \times N$, while edge $v_3t$ is present at point $u \times N + 3$ for each $u \in N(v)$.

* Finally, all temporal edges have delay one.

Note that we can construct $H_G$ from $G$ in $O(n+m)$ time.

We claim that $G$ contains a triangle if and only if the shortest duration for reaching $t$ from $s$ equals 4. Indeed, if $uvw$ is a triangle of $G$, then there exists a temporal path starting at time $uN$, going by vertices $s, u_1, v_2, w_3, t$, with zero waiting time and total duration 4. Conversely, assume the existence of a temporal path $P$ from $s$ to $t$, with total duration at most 4. As edges have delay 1, it must have 4 edges at most, which is the least it can have as $V_1, V_2, V_3$ are vertex separators of the underlying graph (i.e. the removal of any $V_i$ for $i \in [3]$ disconnects $s$ from $t$). We can thus write $P = s, u_1, v_2, w_3, t$ for a triplet $u, v, w \in V$ satisfying $uv, vw \in E$. This path has $su_1$ and $w_3t$ as first and last edges respectively. Then, the starting time of $P$ must be $u \times N$ and edge $w_3t$ must be present at time $uN + 3$ which happens only when $u \ne v$ (since $G$ is loopless) and $u \in N(v)$. Therefore, $G$ contains the triangle $uvw$. This proves the claim. $\square$

<figure><img src="image_2.png" /></figure>
Note that the above proof does not hold with delay zero. If we consider zero delays in the above reduction, then the fastest path from $s$ to $t$ has duration 3 if and only if $G$ contains an odd cycle which is an easier problem than detecting a triangle (it can be tested in linear time). However, if we construct a directed temporal graph $H'$ where all underlying edges are directed from $s$ to $V_1$, from $V_1$ to $V_2$, from $V_2$ to $V_3$ and from $V_3$ to $t$, then it holds that $H'$ contains a temporal st-path of duration 3 if and only if $G$ contains a triangle. We can thus state the following.

Can this Theorem 2 be extended to a hardness of approximation result?

**Theorem 3.** If, for every $\varepsilon > 0$, there is no combinatorial $O(n^{3-\varepsilon})$-time algorithm for detecting a triangle in a graph, then for every $\varepsilon' > 0$, there is no combinatorial $O((nM)^{1-\varepsilon'})$-time algorithm for computing a fastest temporal path in a directed temporal graph, even if all temporal edges have delay zero.

The proof is almost identical to that of Theorem 2 and is left to the reader.

# 4 Fastest temporal path in a zero-delay undirected temporal graph

Given a temporal graph $G$ and a pair of distinct vertices $s$ and $t$ in this graph, we define the st-profile $P_{st}$ as the function $P_{st}(\tau)$ associating each departure time $\tau$ from $s$ to the earliest arrival time at $t$, in other words, $P_{st}(\tau)$ is the minimum arrival time of any temporal path leaving $s$ at a time no earlier than $\tau$. This function is non-decreasing and piece-wise linear. Furthermore, the slope of each linear piece is either zero or one. The reason is that we can define a profile function $E_{uv}$ for each underlying edge $uv$. The slope is one in intervals where the edge is present: for each temporal edge $(u, v, \tau, \tau_2, \delta)$, the earliest arrival time in $V$ is $\tau + \delta$ for $\tau \in [\tau_1, \tau_2]$. The slope is zero in intervals where it is not present, as the earliest arrival is $\tau_1 + \delta$ for $\tau < \tau_1$ if the next presence of $uv$ is during interval $[\tau_1, \tau_2]$ with delay $\delta$. Similarly, the profile function $f_P$ of a path $v_1, \dots, v_k$ can be obtained by composition of $E_{v_1v_2}, \dots, E_{v_{k-1}v_k}$, resulting in a polyline whose slopes are obtained by multiplying slopes of the composing function and must be in $\{0, 1\}$. Finally, we have $P_{st} = \min_{P \in \mathcal{P}} f_P$ which is thus also a polyline with slopes in $\{0, 1\}$. See [8] for more details.

One way to represent this function is by a collection of triples $\{(\alpha_i, \beta_i, s_i)\}_{i=1}^k$, where $(\alpha_i)_{i=1}^k$ is non-decreasing, $\beta_i = P_{st}(\alpha_i)$ and for every $\tau \in (\alpha_{i-1}, \alpha_i]$, we have $P_{st}(\tau) = \beta_i + s_i(\tau - \alpha_i)$ where we define $\alpha_0 = -\infty$. The minimum collection of such triples is what we call a minimal representation of the st-profile. Note that when $s = t$, the profile is the identity function and requires a specific representation. For a detailed study of a general algorithm to find the profile of a pair of vertices in an interval temporal graph with arbitrary delays in $O((n \log n + m)M)$ time, we refer the reader to [8].

**Theorem 4.** Given an undirected interval temporal graph $G$ with $M$ temporal edges having all zero delay, and two vertices $s$ and $t$, it is possible to compute in $\tilde{O}(M)$ time a fastest temporal path from $s$ to $t$.

To prove the above theorem, we first propose a profile algorithm that given the list of temporal edges of an interval temporal graph $G = (V, E)$ and two distinct vertices $s, t \in V$, computes a minimal representation of the profile function $P_{st}$ from $s$ to $t$. The idea of the algorithm is to perform a time scan of temporal edge starts and ends while maintaining connected components for edges present at time $\tau$. We also maintain for each connected component $c$ the last departure time $LDT[c]$ allowing to reach it at time $\tau$ from $s$. In other words, $LDT[c]$ is the maximum time $\lambda$ such that there exists a temporal path from $s$ to any vertex $w$ in the component that starts at time $\lambda$ and arrives no later than time $\tau$. Note that this definition does not depend on $w$: such a temporal path to $w$ can be extended to a temporal walk that arrives at any other vertex of the component at time $\tau$ since all edges of the component are present at time $\tau$ and have zero delay. (And a temporal path can be extracted from that temporal walk by waiting instead of following any loop.)
For that purpose we consider each temporal edge $(u, v, \tau_1, \tau_2, 0)$ as two *events*: a *starting event* (resp. *ending event*) which occurs when the edge starts at time $\tau_1$ (resp. ends at time $\tau_2$) and which is defined as the quadruple $(u, v, \tau_1, \text{start})$ (resp. $(u, v, \tau_2, \text{end})$). As we consider an undirected temporal graph $G$, we generate only one starting event and one ending event for each pair of symmetrical temporal edges. We assume that the temporal graph $G$ is given as a sorted event list, ordered by the time of the events (i.e., the third coordinate). If several events share the same time, starting events appear before ending events, breaking ties arbitrarily among events of the same type. Note that this list can easily be obtained from the list of temporal edges of $G$ in $O(M \log M)$ time using sorting.

We then make use of the dynamic connectivity algorithm of [15] that allows to dynamically add and remove edges from a graph in poly-logarithmic amortized time. We rely on the fact that it maintains a rooted spanning tree for each connected component (the authors refer to [14] for that part). We can thus assume that a procedure $CC(u)$ allows to retrieve in $O(\log n)$ time the ID of the root of the spanning tree of the component of $u$. We use this ID (a number between 1 and $n$) to identify the component, so that the expression $CC(u) = CC(v)$ allows to test whether $u$ and $v$ are in the same connected component. We further let $CC\_AddEdge(uv)$ and $CC\_RemoveEdge(uv)$ denote the procedures that allow dynamic updates of edges of the graph with $O(\log^2 n)$ amortized time complexity. We let $CC\_Init(n)$ denote the initialization procedure for an empty graph with $n$ vertices. Processing the event list in order, we can thus update the graph of edges present at the time of each event.

The update of last departure times is then rather simple. When two components merge because of the appearance of an edge $uv$ at time $\tau$, the last departure time $LDT[c]$ of the resulting component $c$ is set to the maximum of the last departure times of the components of $u$ and $v$ before merging since a temporal path reaching one component can now be extended to reach any node in the other component. When a component splits because of the disappearance of an edge $uv$ at time $\tau$, the two new components get same last departure time as the component before splitting since temporal paths reaching that component are still valid until time $\tau$. Special care has to be taken concerning the connected component of the source $s$ for which the last departure time is always the time $\tau$ of the current event. Obtaining the last departure time $\lambda$ of the connected component of $t$ after an event at time $\tau$ basically indicates that $P_{st}(\lambda) \le \tau$. We will see that when a higher value of $\lambda$ is observed, $\tau$ corresponds to the earliest arrival time when departing at $\lambda$ and we then have $P_{st}(\lambda) = \tau$. Each time an event affects the connected component of the target $t$, we update a list *Prof* of triples accordingly so that it represents the profile $P_{st}$ up to that event. See the pseudo-code of Algorithm 1 for more details.

**Proposition 1.** Given an undirected interval temporal graph $G$ with $M$ temporal edges having all zero delay, and two vertices $s$ and $t$, Algorithm 1 computes a minimal representation of the *st*-profile in $O(M(\log M + \log^2 n))$ time.

First note that Theorem 4 easily follows from Proposition 1 since the duration of a fastest temporal *st*-path as well as the starting time $\lambda$ of such a fastest temporal path can easily be obtained by scanning the *st*-profile in $O(M)$ time. We can then find a fastest *st*-path departing at time $\lambda$ by computing an earliest-arrival *st*-path departing at time $\lambda$ in $O(M \log M)$ time. Indeed, after an $O(M \log M)$ pre-processing for obtaining for each underlying edge $uv$ the sorted list of temporal edges connecting $uv$, we compute such a path through a temporal version of Dijkstra's algorithm [11, 4] in $O(m \log M + n \log n)$ time. Note that the $\log M$ factor accounts for the time required to find with binary search the first temporal edge connecting $uv$ that can be traversed at a certain time $\tau$ for a given neighbor $v$ of a node $u$ reached at time $\tau$. It also takes into account the time to pre-process temporal edges in order to remove overlaps, see [17] for more details.

*Proof of Proposition 1.* Considering all events up to an event $e \in E$, let $G^e$ be the temporal graph with the same set of vertices as $G$ and all temporal edges $(u, v, \tau_1, \tau_2)$ of $G$ such that the event $(u, v, \tau_1, \text{start})$ is not after $e$ in the event list $E$. The temporal edges of $G^e$ that correspond to temporal edges of $G$ whose ending events come after $e$ in $E$ are called *unclosed temporal edges* as their ending events have not been processed yet. We let $\tau^e$ denote the time at which event $e$ occurs.
**Input:** A temporal graph $G$ given by a sorted list $E$ of edge events with vertex set $V(G) = [n]$, a source node $s \in V(G)$ and a target node $t \in V(G) \setminus \{s\}$.

**Output:** The st-profile.

1. $Prof := \emptyset$ // initial st-profile

2. $CC\_Init(n)$ // initially empty graph

3. $LDT[c] := -\infty$ for all $c \in [n]$ // last departure time of a walk from $s$ to any vertex in a connected component $c$

4. For $e = (u, v, \tau, evt) \in E$ do
5. &nbsp;&nbsp;&nbsp;&nbsp; $LDT[CC(s)] := \tau$ // $s$ can reach its component at time $\tau$
6. &nbsp;&nbsp;&nbsp;&nbsp; $\lambda_t := LDT[CC(t)]$ // last departure time to reach $t$
7. &nbsp;&nbsp;&nbsp;&nbsp; $st\_connected := CC(s) = CC(t)$ // true if $s$ and $t$ are connected

8. &nbsp;&nbsp;&nbsp;&nbsp; If $evt = start$ then // edge $uv$ appears
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lambda := \max\{LDT[CC(u)], LDT[CC(v)]\}$
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $CC\_AddEdge(uv)$
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $c := CC(u)$ // connected component containing $u$ and $v$
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $LDT[c] := \lambda$
13. &nbsp;&nbsp;&nbsp;&nbsp; If $CC(t) = c$ and $\lambda > \lambda_t$ then $Prof := Prof \cup \{(\lambda, \tau, 0)\}$

14. &nbsp;&nbsp;&nbsp;&nbsp; else // edge $uv$ disappears
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $c := CC(u)$ // connected component containing $u$ and $v$
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lambda := LDT[c]$
17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $CC\_RemoveEdge(uv)$
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $LDT[CC(u)] := \lambda$
19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $LDT[CC(v)] := \lambda$

20. &nbsp;&nbsp;&nbsp;&nbsp; If $st\_connected$ then $Prof := Prof \cup \{(\tau, \tau, 1)\}$

21. Return $Prof$

<caption>**Algorithm 1:** One-to-one profile.</caption>

We define the last departure time $\lambda^e(w)$ from $s$ to reach $w$ at $e$ or before in $G^e$ as the maximum time $\lambda$ such that there exists an $sw$-walk departing at time $\lambda$ in $G^e$ and arriving no later than $\tau^e$. We also denote by $P_{st}^e$ the st-profile in $G^e$ up to $\tau^e$ (i.e. with support restricted to $(-\infty, \tau^e]$) and let $last(P_{st}^e)$ denote the maximum time $\tau \le \tau^e$ for which $P_{st}^e(\tau)$ is defined ($last(P_{st}^e) = -\infty$ when $G^e$ does not contain any temporal path from $s$ to $t$). Similarly, we use $CC^e$, $LDT^e$ and $Prof^e$ to refer to the values stored in $CC$, $LDT$ and $Prof$ respectively after the algorithm has processed the event $e$. We aim at proving the following claim.

**Claim 1.** For each event $e$, we have $LDT^e[CC^e(w)] = \lambda^e(w)$ for any vertex $w \ne s$ and $Prof^e$ is a representation of $P_{st}^e$.

Note that applying this claim to the last event $l$ proves the correctness of Algorithm 1 as it ensures that $Prof^l$ is a representation of the st-profile in $G = G^l$. The complexity of the algorithm directly follows from the amortized time complexities of the dynamic connected component procedures.

Proposition 1 will thus follow from the proof of this claim. Before proving it, let us state some simpler claims.

We shall rely on the correctness of the dynamic connected component procedures which implies that $CC^e(w) \in [n]$ uniquely identifies the connected component of $w$ in the graph induced by the temporal edges that are present in $G$ at time $\tau^e$ and whose ending event is after $e$ in $E$. The ordering of $E$, with all starting events at a given time $\tau$ preceding all ending events at time $\tau$, implies that these temporal edges are exactly the unclosed temporal edges of $G^e$. We say that $u$ and $v$ are $e$-connected when $CC^e(u) = CC^e(v)$, or equivalently when they are connected through unclosed temporal edges of $G^e$ which leads to the following claim.
**Claim 2.** For any pair $u, v$ of e-connected vertices (i.e. $CC^e(u) = CC^e(v)$), there exists a temporal $uv$-path in $G^e$ that departs and arrives at time $\tau^e$.

This simply follows from the fact that all unclosed temporal edges of $G^e$ are present at time $\tau^e$. This then leads to the following.

**Claim 3.** For any pair $u, v$ of e-connected vertices (i.e. $CC^e(u) = CC^e(v)$), we have $\lambda^e(u) = \lambda^e(v)$.

Consider a temporal *su*-path $P$ in $G^e$ departing at time $\lambda^e(u)$ and arriving no later than $\tau^e$. According to Claim 2, $P$ can be extended by a temporal *uv*-path. The resulting temporal walk departs at time $\lambda^e(u)$ which implies $\lambda^e(v) \ge \lambda^e(u)$. Symmetrically, we also have $\lambda^e(u) \ge \lambda^e(v)$ and the claim follows.

The following is a simple consequence of the definition of $G^e$.

**Claim 4.** For any two consecutive events $e, f$ in $E$, we have either $G^e = G^f$ if $f$ is an ending event, or if $f$ is a starting event $G^f$ differs from $G^e$ by the addition of the two symmetrically temporal edges associated to $f$.

As a direct corollary, we obtain the following since any temporal path in $G^e$ is also a temporal path in $G^f$.

**Claim 5.** For any two events $e$ and $f$ such that $e$ precedes $f$ in $E$, and any vertex $w$, we have $\lambda^f(w) \ge \lambda^e(w)$.

We also obtain $P_{st}^f(\lambda) \le P_{st}^e(\lambda)$ for any time $\lambda \le \text{last}(P_{st}^e)$. We also have $P_{st}^e(\lambda) \le \tau^e$ since a temporal path arriving after $\tau^e$ in $G^e$ uses only unclosed temporal edges after $\tau^e$, and since these edges start at $\tau^e$ or before we can transform the temporal path into one arriving at $\tau^e$. This implies that we have equality of profiles for $\lambda \le \text{last}(P_{st}^e)$ since no temporal path in $G^f$ can arrive before $P_{st}^e(\lambda) \le \tau^e$ as the possible additional temporal edges of $G^f$ start at $\tau^e$ or later. We can thus state the following.

**Claim 6.** For any two events $e$ and $f$ such that $e$ precedes $f$ in $E$, and any time $\lambda \le \text{last}(P_{st}^e)$, we have $P_{st}^f(\lambda) = P_{st}^e(\lambda)$.

We now prove Claim 1 by induction on the number of events processed. Initially, we consider an empty temporal graph $G^0 = (V(G), \emptyset)$ (with no temporal edge). As expected, we initially have $\text{LDT}^e[CC^e(w)] = -\infty$ for $w \ne s$ and $\text{Prof}$ is empty reflecting that there exists no temporal walk from $s$ to $t$ in $G^0$. We assume the induction hypothesis for event $e$, that is $\text{LDT}^e[CC^e(w)] = \lambda^e(w)$ for any vertex $w \ne s$ and $\text{Prof}^e$ is a representation of $P_{st}^e$. Let us consider the next event $f$.

**Ending event case.** First suppose that $f$ is an ending event $(u, v, \tau^f, \text{end})$ generated for the temporal edge $f' = (u, v, \tau_1, \tau^f)$ of $G$. We have $G^e = G^f$ by Claim 4. Consider a temporal *sw*-path $P = (e_1, \tau_1), \dots, (e_k, \tau_k)$ in $G^f$. For each $\tau_i > \tau^e$, the corresponding temporal edge $e_i$ must correspond to an unclosed temporal edge of $G^e$, and if we replace each such $\tau_i$ by $\tau^e$, we then obtain a valid temporal path in $G^e$ arriving at time $\tau^e$ instead of $\tau_k$. For all $w$ satisfying $\lambda^f(w) \le \tau^e$, this implies $\lambda^e(w) \ge \lambda^f(w)$ and thus $\lambda^e(w) = \lambda^f(w)$ by Claim 5. Observe that $w = t$ leads to $\lambda^e(t) = \lambda^f(t)$ if $\lambda^f(t) \le \tau^e$.

Now consider a vertex $w \ne s$ such that $\lambda^f(w) > \tau^e$ and let $P = (e_1, \tau_1), \dots, (e_k, \tau_k)$ be a temporal *sw*-path departing at time $\tau_1 = \lambda^f(w) > \tau^e$ in $G^f$. As $P$ is a temporal path, we have $\tau_i > \tau^e$ for all $i \in [k]$ and $P$ uses only unclosed temporal edges. We thus have $CC^e(w) = CC^e(s)$. Indeed, for any node $w$ satisfying $CC^e(w) = CC^e(s)$, there exists a temporal *sw*-path departing at time $\tau^f$ and arriving at time $\tau^f$, implying $\lambda^f(w) = \tau^f$. As we updated $\text{LDT}[CC^e(s)]$ to $\tau^f$ at Line 5, and report this value to both $CC^f(u)$ and $CC^f(v)$ if $CC^e(s) = CC^e(u)$, we have $\text{LDT}^f[CC^f(w)] = \lambda^f(w)$ for all $w$ satisfying $CC^e(w) = CC^e(s)$.

Note that we have $\text{LDT}^f[CC^f(w)] = \text{LDT}^e[CC^e(w)]$ as long as $CC^e(w) \ne CC^e(s)$ since $\text{LDT}[CC^e(w)]$ is not modified if $CC^e(w) \ne CC^e(u)$ and the value of $\text{LDT}^e[CC^e(w)]$ is copied to $\text{LDT}^f[CC^f(w)]$ otherwise. We have thus proved $\text{LDT}^f[CC^f(w)] = \lambda^f(w)$ for all $w \ne s$.
By Claim 6, we have $P_{st}^f(\lambda) = P_{st}^e(\lambda)$ for $\lambda \le \text{last}(P_{st}^e)$. Moreover, as observed above, if $\lambda^f(t) \le \tau^e$, we have $\lambda^f(t) = \lambda^e(t) \le \text{last}(P_{st}^e)$ and $P_{st}^f = P_{st}^e$. The only case where $P_{st}^f$ differs from $P_{st}^e$ is thus when $CC^e(t) = CC^e(s)$, that is when *st-connected* is true. This implies that we have $\text{last}(P_{st}^e) = \tau^e$ and $P_{st}^e(\tau^e) = \tau^e$, and that $P_{st}^f$ the identity over $[\tau^e, \tau^f]$ as reflected by the addition of the triple $(\tau^f, \tau^f, 1)$ at the end of *Prof* in that case at Line 20. *Prof*^f is thus a valid representation of $P_{st}^f$.

**Starting event case.** Now suppose that $f$ is a starting event $(u, v, \tau^f, \text{start})$ for the temporal edge $f' = (u, v, \tau_f, \tau_2)$ of $G$. By Claim 4, $G^f$ then differs from $G^e$ by having the two extra temporal edges $f'$ and its symmetrical temporal edge $f'' = (v, u, \tau_f, \tau_2)$.

First consider a vertex $w$ which is $f$-connected to $s$, i.e. satisfying $CC^f(w) = CC^f(s)$. Its last departure time should be updated to $\tau^f$. The updates at Lines 5 and 12 ensure that we indeed get $\text{LDT}^f[CC^f(w)] = \tau^f$.

Now consider a vertex $w$ which is $f$-connected to $u$ and $v$, but not to $s$, i.e. $CC^f(w) = CC^f(u) = CC^f(v)$ and $CC^f(w) \ne CC^f(s)$. Claim 3 implies $\lambda^f(w) = \lambda^f(u) = \lambda^f(v)$. We then prove $\lambda^f(u) = \lambda^f(v) = \max\{\lambda^e(u), \lambda^e(v)\}$. As $\lambda^f(u) \ge \lambda^e(u)$ and $\lambda^f(v) \ge \lambda^e(v)$ by Claim 5, we get $\lambda^f(u) = \lambda^f(v) \ge \max\{\lambda^e(u), \lambda^e(v)\}$. Consider a temporal *sv-path* $P = (e_1, \tau_1), \dots, (e_k, \tau_k)$ departing at time $\tau_1 = \lambda^f(v)$ in $G^f$. As $P$ is a temporal path arriving in $v$, it does not traverse $f''$. If this path does not traverse $f'$, it is also a temporal path of $G^e$ and we have $\lambda^e(v) \ge \lambda^f(v)$. Otherwise, its prefix before $f'$ is a temporal *su-path* of $G^e$ and we get $\lambda^e(u) \ge \lambda^f(v) = \lambda^f(u)$. In both cases, we have $\max\{\lambda^e(u), \lambda^e(v)\} \ge \lambda^f(u)$ and we indeed have equality. The induction hypothesis and the update by Lines 9 and 12 thus ensures $\text{LDT}^f[CC^f(w)] = \lambda^f(w)$ in this case.

Finally, consider a vertex $w$ satisfying $CC^f(w) \ne CC^f(u)$ and $CC^f(w) \ne CC^f(s)$. Let $P = (e_1, \tau_1), \dots, (e_k, \tau_k)$ be a temporal *sw-path* departing at time $\tau_1 = \lambda^f(w)$ in $G^f$. We now show that $P$ cannot contain $f'$ or $f''$. Suppose for the sake of contradiction that there exists $i$ such that $e_i = f'$ or $e_i = f''$, we then have $\tau_i = \tau^f$ and $\tau_j \ge \tau^f$ for $j \ge i$. This implies that all temporal edges after $e_i$ are unclosed, in contradiction with $CC^f(w) \ne CC^f(u)$. We thus deduce that $P$ is also a temporal path of $G^e$, leading to $\lambda^e(w) \ge \lambda^f(w)$ and then $\lambda^f(w) = \lambda^e(w)$ by Claim 5. As $\text{LDT}[CC^f(w)]$ is not modified in that case, the induction hypothesis leads to $\text{LDT}^f[CC^f(w)] = \lambda^f(w)$. We have thus proved $\text{LDT}^f[CC^f(w)] = \lambda^f(w)$ for all $w$.

Let us now consider the *st-profile* in $G^f$. $P_{st}^f$ is the identity during interval $[\tau^e, \tau^f]$ when $CC^e(s) = CC^e(t)$ in correspondence with the addition of $(\tau^f, \tau^f, 1)$ to *Prof* at Line 20 in that case. Note that we then have $\text{last}(P_{st}^e) = \tau^e$ and $P_{st}^e(\tau^e) = \tau^e$.

If $t$ is connected to $u$ or $v$, we have $\lambda^f(t) = \text{LDT}^f[CC^f(u)] = \lambda$ as we just proved. Note that we have $\lambda_t = \text{LDT}^e[CC^e(t)] = \lambda^e(t)$ by induction hypothesis. If $\lambda > \lambda_t$, this is in correspondence with the addition of $(\lambda, \tau^f, 0)$ at Line 13 as a temporal *st-path* departing at time $\lambda$ must use $f'$ or $f''$ and cannot arrive before $\tau^f$. Note that we have $\lambda = \tau^f = \lambda_t$ when $CC^e(s) = CC^e(t)$ and the triple is not added in that case. Otherwise, $\lambda \le \lambda_t$ can only occur when $\lambda^f(t) = \lambda^e(t)$ by Claim 5. We then have $\lambda^f(t) = \text{last}(P_{st}^e)$ implying $P_{st}^f = P_{st}^e$ which justifies to not modify *Prof* in that case.

If $t$ is not in the connected component of neither $s$, nor $u$, nor $v$, then $P_{st}^f = P_{st}^e$ since a temporal *st-path* in $G^f$ cannot traverse $f'$ or $f''$ in that case as proved above, and must also be an *st-path* in $G^e$ with the same departure time. This is indeed reflected by the fact that *Prof* is not modified in that case, yielding to $\text{Prof}^f = \text{Prof}^e$. We finally obtain that $\text{Prof}^f$ is a valid representation of $P_{st}^f$ in all cases. This concludes our proof by induction of Claim 1. $\square$

# 5 Lower bound for shortest temporal path

**Theorem 5.** If, for every $\varepsilon > 0$, there is no combinatorial $O(n^{3-\varepsilon})$-time algorithm for detecting a triangle in a graph, then for every $\varepsilon' > 0$, there is no combinatorial $O((nM)^{1-\varepsilon'})$-time algorithm for computing a shortest temporal path in a temporal graph, even if the temporal graph is undirected and all temporal edges have delay zero.

*Proof.* Let $G = (V, E)$ be an instance of TRIANGLE DETECTION and suppose $V = \{v_1, \dots, v_n\}$. A
temporal graph $H_G$ is constructed as follows. Here, a *permanent temporal edge* between vertices $u$ and $v$ indicates that the edge is present during the interval $[1, n]$. All delays are zero.

* The vertex set of $H_G$ consists of the vertices $s, t$, and 4 disjoint copies of $V$, denoted $V_1, \dots, V_4$. For $j \in \{1, 2, 3, 4\}$ and $i \in V$, let $v_j^i$ represent the vertex $v_j$ in the copy $V_i$.

* In $V_1$ and $V_4$, permanent temporal edges are defined to form a path that respects the vertex ordering. Specifically, for $j \in \{1, 4\}$ and $i \in \{1, \dots, n-1\}$, we add a permanent temporal edge between $v_i^j$ and $v_{i+1}^j$. Additionally, permanent temporal edges are defined to connect the source vertex $s$ to $v_n^1$ and the target vertex $t$ to $v_1^4$.

* For each edge $v_i v_j \in E$ with $i < j$, the temporal edges $v_i^1 v_j^2$ and $v_j^3 v_i^4$ are both present at time $i$. Additionally, a permanent temporal edge $v_i^2 v_j^3$ is added.

Observe that $H_G$ can be constructed in $O(n+m)$ time, where $m$ is the number of edges of $G$. The correctness of the reduction comes from the following claim. The theorem thus follows from its proof.

**Claim 7.** *There is a triangle in $G$ if and only if there exists a temporal path in $H_G$ from $s$ to $t$ using at most $n+4$ edges.*

First, suppose there is a triangle in $G$ formed by the vertices $v_{i_1}, v_{i_2}, v_{i_3}$ with $i_1 < i_2 < i_3$. Using the permanent edges within $V_1$, we can construct a temporal path starting at $s$ and arriving at $v_{i_1}^1$ at time $1 \le i_1$. Let this path be denoted by $P_1$ and note that it contains $n+1-i_1$ edges. By the existence of the triangle, we know that the temporal edges $e_1 = (v_{i_1}^1, v_{i_2}^2, i_1, i_1, 0), e_2 = (v_{i_2}^2, v_{i_3}^3, 1, n, 0), e_3 = (v_{i_3}^3, v_{i_1}^4, i_1, i_1, 0)$ form a temporal path $(e_1, i_1), (e_2, i_1), (e_3, i_1)$ in $H_G$. Denote this temporal path as $P_2$. Using the permanent edges within $V_4$, we can construct a temporal path $P_3$ from $v_{i_1}^4$ to $t$ that uses $i_1$ edges. The paths $P_1, P_2$, and $P_3$ are constructed such that they can be concatenated into a single temporal path from $s$ to $t$. The total number of edges in this concatenated path is $n+4$. See Figure 2 for an illustration of such a temporal path.

<figure><img src="image_3.png" /><figcaption>Figure 2: A temporal path in $H_G$ corresponding to a triangle in $G$.</figcaption></figure>

Now, suppose there exists a temporal path $P$ from $s$ to $t$ of length at most $n+4$. Let $P'$ be the temporal path obtained from $P$ by removing its first and last edges (those incident to $s$ and $t$ respectively). Let $e$ be the first temporal edge of $P'$ that is not within $V_1$, and let $g$ be the last temporal edge of $P$ that is not within $V_4$. By the structure of $H_G$, $e$ connects a vertex in $V_1$, say $v_{i_1}^1$, with a vertex in $V_2$, say $v_{i_2}^2$, and it is present only at time $i_1$. Similarly, $g$ is incident to vertices $v_{i_3}^3$ and $v_{i_4}^4$, and it is present only at time $i_4$. Moreover, by definition, $g$ appears after $e$ in $P$. Thus, $i_1 \le i_4$.
Finally, observe that the distance from $s$ to $v_{i_1}^1$ in the underlying graph is at least $(n+1)-i_1$, the distance from $v_{i_1}^1$ to $v_{i_4}^4$ is at least 3, and the distance from $v_{i_4}^4$ to $t$ is at least $i_4$. This implies that $P$ uses at least $n+4+(i_4-i_1)$ temporal edges. Since the length of $P$ is at most $n+4$, we get that $i_4 \le i_1$. We thus have $i_1 = i_4$. Now, the three temporal edges that $P$ uses between $v_{i_1}^1$ and $v_{i_1}^4$ is 3 connect the pairs $v_{i_1}^1 v_{i_2}^2, v_{i_2}^2 v_{i_3}^3$ and $v_{i_3}^3 v_{i_1}^4$. By the way that $H_G$ is constructed, we have that $v_{i_1}, v_{i_2}, v_{i_3}$ form a triangle in $G$. □

# 6 Conclusion

We have presented non-trivial lower bounds showing a complexity gap between point temporal graphs and interval temporal graphs. They also show a complexity gap between the computation of a foremost temporal path and that of a fastest temporal path. As far as we know, these are the first results proving these gaps. Several questions arise from this work.

First, can we close the gap between our $\Omega(nM)$ lower bound for the computation of a fastest temporal path and the $\tilde{O}(mM)$ upper bound given by the best-known algorithm?

Combinatorial algorithms for computing a shortest path in a graph can usually be extended to compute one-to-all shortest paths. In the case of uniform zero delay, can we similarly hope to find an $\tilde{O}(M)$ algorithm for computing one-to-all fastest durations, i.e., given a source vertex $s$, an algorithm that computes the duration of a fastest temporal path from $s$ to each possible target vertex $t$? Note that we cannot hope to turn Algorithm 1 into a one-to-all profile algorithm with the same complexity, since a profile can be of size $\Omega(M)$. But it can easily be turned into an $\tilde{O}(nM)$-time algorithm for one-to-all profiles. More generally, does this complexity also apply to interval temporal graphs with constant delays? Note that a positive answer would also apply to the computation of one-to-all fastest durations, and thus would probably also solve our first question.

# References

[1] Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. *Journal of Computer and System Sciences*, 107:108-123, 2020. doi:10.1016/j.jcss.2019.08.002.

[2] Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. *Appl. Netw. Sci.*, 5(1):73, 2020. URL: https://doi.org/10.1007/s41109-020-00311-0, doi:10.1007/S41109-020-00311-0.

[3] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot. On computing pareto optimal paths in weighted time-dependent networks. *Inf. Process. Lett.*, 168:106086, 2021. URL: https://doi.org/10.1016/j.ipl.2020.106086, doi:10.1016/J.IPL.2020.106086.

[4] Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. *Int. J. Found. Comput. Sci.*, 14(2):267-285, 2003. doi:10.1142/S0129054103001728.

[5] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. *Int. J. Parallel Emergent Distributed Syst.*, 27(5):387-408, 2012. doi:10.1080/17445760.2012.668546.

[6] Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, *46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece*,
volume 132 of LIPIcs, pages 134:1-134:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.134, doi:10.4230/LIPICS.ICALP.2019.134.

[7] Kenneth L. Cooke and Eric Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14(3):493-498, 1966. URL: https://doi.org/10.1016/0022-247X(66)90009-6.

[8] Frank Dehne, Masoud T. Omran, and Jörg-Rüdiger Sack. Shortest paths in time-dependent FIFO networks. Algorithmica, 62(1-2):416-435, 2012. URL: https://doi.org/10.1007/s00453-010-9461-6, doi:10.1007/S00453-010-9461-6.

[9] Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly simple and fast transit routing. In Vincenzo Bonifaci, Camil Demetrescu, and Alberto Marchetti-Spaccamela, editors, Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, volume 7933 of Lecture Notes in Computer Science, pages 43-54. Springer, 2013. doi:10.1007/978-3-642-38527-8_6.

[10] Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection scan algorithm. ACM J. Exp. Algorithmics, 23, 2018. doi:10.1145/3274661.

[11] Stuart E. Dreyfus. An appraisal of some shortest-path algorithms. Oper. Res., 17(3):395-412, 1969. URL: https://doi.org/10.1287/opre.17.3.395, doi:10.1287/OPRE.17.3.395.

[12] Luca Foschini, John Hershberger, and Subhash Suri. On the complexity of time-dependent shortest paths. Algorithmica, 68(4):1075-1097, 2014. URL: https://doi.org/10.1007/s00453-012-9714-7, doi:10.1007/S00453-012-9714-7.

[13] Roman Haag, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Feedback edge sets in temporal graphs. Discrete Applied Mathematics, 307:65-78, 2022. doi:10.1016/j.dam.2021.09.029.

[14] Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. doi:10.1145/320211.320215.

[15] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. doi:10.1145/502090.502095.

[16] Petter Holme. Modern temporal network theory: A colloquium. CoRR, abs/1508.01303, 2015. URL: http://arxiv.org/abs/1508.01303, arXiv:1508.01303.

[17] Anuj Jain and Sartaj K. Sahni. Algorithms for optimal min hop and foremost paths in interval temporal graphs. Appl. Netw. Sci., 7(1):60, 2022. URL: https://doi.org/10.1007/s41109-022-00499-3, doi:10.1007/S41109-022-00499-3.

[18] David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. doi:10.1006/jcss.2002.1829.

[19] Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min., 8(1):61:1-61:29, 2018. URL: https://doi.org/10.1007/s13278-018-0537-7, doi:10.1007/S13278-018-0537-7.

[20] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252. SIAM, 2018. doi:10.1137/1.9781611975031.80.
[21] George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs. *J. Comput. Syst. Sci.*, 137:1–19, 2023. URL: https://doi.org/10.1016/j.jcss.2023.04.005, doi:10.1016/J.JCSS.2023.04.005.

[22] Othon Michail. An introduction to temporal graphs: An algorithmic perspective. *Internet Math.*, 12(4):239–280, 2016. doi:10.1080/15427951.2016.1177801.

[23] 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.

[24] Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. *J. ACM*, 65(5):27:1–27:38, 2018. doi:10.1145/3186893.

[25] 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.

[26] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient algorithms for temporal path computation. *IEEE Trans. Knowl. Data Eng.*, 28(11):2927–2942, 2016. doi:10.1109/TKDE.2016.2594065.