Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems

Aubian, Guillaume; Brunelli, Filippo; Dragan, Feodor F.; Ducoffe, Guillaume; Habib, Michel; Ibiapina, Allen; Viennot, Laurent

doi:10.4230/LIPIcs.SAND.2026.5

Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems

Guillaume Aubian IRIF, CNRS & Université Paris Cité, France Filippo Brunelli European Commission – Joint Research Centre (JRC), Brussels, Belgium Feodor F. Dragan

Kent State University, Department of Computer Science, Kent, Ohio, USA Guillaume Ducoffe

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

IRIF, CNRS & Université Paris Cité, France Allen Ibiapina IRIF, CNRS & Université Paris Cité, France Laurent Viennot

Inria, DI ENS, Paris, France

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, whereas in the more general interval model, edges can be present over specific 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 implications for complexity. 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 also show a similar complexity gap for computing a shortest temporal path, i.e., a temporal path with a minimum number of edges. Here our lower bound matches known upper bounds up to a logarithmic factor. Interestingly, we show that near-linear time for fastest temporal path computation is possible in the interval model when it is restricted to uniform delay zero, i.e., when traversing an edge is instantaneous. However, this special case is not exempt from our lower bound for shortest temporal path computation. These two results should be contrasted with the computation of a foremost temporal path, i.e., a temporal path that arrives as early as possible. It is well known that this computation can be solved in near-linear time in both models. We also show that there is no gap in testing the all-to-all temporal connectivity of a temporal graph. We demonstrate a quadratic lower bound that applies to both the interval and point models and aligns with the existing upper bounds.

Keywords and phrases:

Temporal graphs, Dynamic networks, Time-dependent networks, Temporal connectivity, Foremost, Fastest or Shortest temporal path, Fine-grained complexity

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Graph algorithms analysis ; Theory of computation

\rightarrow

Shortest paths

Related Version:

Full Version: https://arxiv.org/abs/2501.11380

Funding:

Supported by the French ANR project ANR-22-CE48-0001 (TEMPOGRAL).

DOI:

10.4230/LIPIcs.SAND.2026.5

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

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 time-dependent networks [12] in the context of road networks. They were later re-introduced under various flavors of models, see e.g. [8, 22, 26, 28]. In the simplest model, each edge appears at specific points in time. In the most advanced model, each edge is present for entire time intervals, and the delay for traversing it is given by a time-dependent function, often assumed to be piecewise linear (and, without loss of generality, linear in each interval of appearance). 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 about 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 $\ell$ can be seen as $\ell$ point-by-point appearances. However, the size of the input can then grow by an exponential factor, leading to different complexities 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. [2, 9, 19, 25, 27, 29]. 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. [6, 35]). A temporal path is a path whose edges can be traversed one after another sequentially in time. 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.

First, we observe discrepancies between the two models with respect to the complexity of known algorithms for computing a shortest or a fastest temporal path. They can both be found in near-linear time in the point model [35], while in the interval model the best algorithms for computing a shortest temporal path [6, 24] or a fastest temporal path [14] are slower by a factor depending on the size of the input, $n$ and $m=O(n^{2})$ respectively, if the input has $n$ vertices and the underlying graph has $m$ edges. On the other hand, foremost temporal paths can be computed in near-linear time in both models using a variant of Dijkstra’s algorithm [16, 6]. To the best of our knowledge, no non-trivial lower bounds are known. Thus, we ask whether a slowdown factor proportional to the number of vertices is necessary to compute a fastest or a shortest temporal path in the interval model.

Second, a quadratic lower bound is known for the he natural problem of temporal connectivity, i.e. the existence of a temporal path between any pair of vertices, in the directed point model [13]. Indeed, the best known approach is to perform a single-source foremost temporal path computation for each possible source vertex [4, 1], resulting in time complexity of $\widetilde{\cal O}(nM)$ for a temporal graph with $n$ vertices and $M$ temporal edges in both models. We ask whether the bound holds also in undirected temporal graphs where edges can be traversed in both directions.

The point model has been extensively studied without considering delays (see, e.g., [25, 28]). Temporal paths then classically come in two flavors: strict when times of appearance strictly increase along the path, and non-strict when times of appearance are non-decreasing. These two flavors can equivalently be captured by delays of one and zero respectively. Similarly, the interval model has been extensively studied without delays in the literature about social networks (see, e.g., [23, 22, 26]). Therefore, we pay special attention to the specific cases where all the delays are one and zero, respectively.

Table 1: Summary of known results on the complexity of computing a foremost, fastest or shortest temporal path or testing temporal connectivity in a temporal graph with

n

vertices and

M

temporal edges. In the column structure the abbreviation “TPG” means “temporal graph”. The lower-bounds are given for any

\epsilon>0

under standard fine-grained complexity assumptions. Symbols

\Omega^{*},\Omega^{\times},\Omega^{+}

all stand for

\Omega

under the following respective assumptions:

{\Omega}^{*}

holds under SETH;

{\Omega}^{\times}

holds under the assumption that there is no algorithm that can solve all pairs shortest path (APSP) in truly subcubic time; and

{\Omega}^{+}

applies to combinatorial algorithms assuming that no such algorithm can solve triangle detection in truly subcubic time.

	Point TPG	Interval TPG	Undirected Interval TPG
	Point TPG	Interval TPG	delay zero	delay one
Foremost	$\widetilde{\cal O}(M)$ [16, 6]	$\widetilde{\cal O}(M)$ [16, 6]	$\widetilde{\cal O}(M)$ [16, 6]	$\widetilde{\cal O}(M)$ [16, 6]
Fastest	$\widetilde{\cal O}(M)$ [35, 15]	$\Omega^{\times}((nM)^{1-\varepsilon})$ Th.3, $\widetilde{\cal O}(n^{2}M)$ [14]	$\widetilde{\cal O}(M)$ Th.6	${\Omega^{+}}((nM)^{1-\epsilon})$ Th.4
Shortest	$\widetilde{\cal O}(M)$ [35]	$\Omega^{+}((nM)^{1-\varepsilon})$ Th.2, $\widetilde{\cal O}(nM)$ [6]	${\Omega^{+}}((nM)^{1-\epsilon})$ Th.2	${\Omega^{+}}((nM)^{1-\epsilon})$ Th.2
Connectivity	${\Omega^{*}}((nM)^{1-\epsilon})$ [13] Th.1	$\widetilde{\cal O}(nM)$ [16, 6]	${\Omega^{*}}((nM)^{1-\epsilon})$ Th.1	${\Omega^{*}}((nM)^{1-\epsilon})$ Th.1

Our contribution

We give strong evidence towards a positive answer to both of the above questions. Our first result is a subquadratic reduction from diameter two in graphs to temporal connectivity in point temporal graphs. The former problem consists in testing whether an undirected graph has diameter at most two. It is known to require quadratic time under the Strong Exponential Hypothesis (SETH) [31]. This reduction implies that, for any $\epsilon>0$ , testing temporal connectivity in point temporal graphs with $n$ vertices and $M$ edge appearances requires $\Omega((nM)^{1-\epsilon})$ time unless SETH is false. Our reduction is restricted to undirected point temporal graphs with uniform delay zero, i.e. each edge can be traversed in both directions with delay zero each time it appears. A similar reduction applies to uniform delay one. Obviously, this lower bound holds also for the more general setting of interval temporal graphs. It extends to the undirected case the lower bound of $\Omega(M^{2-\epsilon})$ obtained through a reduction from SAT in [13] for directed point temporal graphs¹¹1The authors of [13] state their lower bound for some $\epsilon$ but their reduction from $k$ -SAT allows to show it for any $\epsilon>0$ (using the definition of SETH, an appropriate $k$ can be chosen for a given $\epsilon>0$ ).. We state a lower bound of $\Omega((nM)^{1-\epsilon})$ for consistency with the upper bound of $\widetilde{\cal O}(nM)$ . However, our reduction uses $M=\Theta(n)$ and also implies a $\Omega(M^{2-\epsilon})$ lower bound.

Our main result is 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 would break the state of the art for several classical problems, including e.g., all pairs shortest path (APSP), the replacement paths problem on weighted directed graphs, and verifying the correctness of a matrix product over the $(\min,+)$ -semiring, among others [34]. 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.

We supplement the latter lower bound with the following refinements for uniform delays zero and one. First, we provide a deterministic “combinatorial” near-linear-time algorithm for finding a fastest temporal path in undirected interval temporal graphs with uniform delay zero. Our algorithm is a rather simple utilization of a dynamic connectivity algorithm. We indeed solve the slightly more technical 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. Second, we show that this restricted setting to undirected temporal graphs with uniform delay zero is the widest possible in which we can expect a near-linear time “combinatorial” algorithm. More precisely, we provide two subcubic reductions from triangle detection in an undirected graph to fastest temporal path computation. One lower bound applies to undirected interval graphs with uniform delay one, and the other applies to 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 [34]. The notion of a “combinatorial” algorithm has no formal definition. Intuitively, it refers to an algorithm which is efficient both theoretically and practically, i.e., whose complexity has a low leading constant. Our reductions imply that a truly subcubic combinatorial algorithm for one of these restricted settings would constitute a breakthrough with respect to Boolean matrix multiplication algorithms [34].

Finally, we provide a reduction from triangle detection in undirected graphs to shortest path computation in interval temporal graphs. This leads to a lower bound of $\Omega((nM)^{1-\epsilon})$ time for combinatorial algorithms. Interestingly, this reduction uses a temporal graph of diameter $\Theta(n)$ , as opposed to our other reductions, which are based on temporal paths of constant length. This is indeed necessary as the algorithm of [6] finds a shortest temporal path in $\widetilde{\cal O}(Dm)$ where $D\leq 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 $\widetilde{\cal O}(M)$ time. Here, our reduction applies to undirected temporal graphs with uniform delay zero. A slight variant applies to those with uniform delay one. We thus do not expect a faster algorithm in these cases.

See Table 1 for a summary of our results and previously known results. Note that our lower bounds for temporal connectivity and shortest temporal path computation are tight with respect to known upper bounds.

More related work.

The difference in complexity between the interval model and the point model has already been noticed in [5] about algorithms solving the profile problem. Profile computation cannot be performed in polynomial time if the delay for traversing a temporal edge is linear [18], but a fastest temporal path can still be computed in $\widetilde{\cal O}(mM)$ time by combining [18] and [14]. The possibility of using dynamic connectivity for computing (instantaneous) strongly connected components is discussed in [30]. The following complexity gap between the point and interval models is shown in [11]: Finding a restless temporal path (where waiting is not allowed) in a point temporal graph is fixed-parameter tractable (FPT) when parameterized by the vertex-interval-membership-width, a temporal graph parameter introduced in [7]. However, it is NP-hard in interval temporal graphs of vertex-interval-membership-width equal to three. Testing if connectivity is maintained in an interval temporal graph with delay zero is studied in [3].

Structure of the paper

After formally introducing temporal graphs, we first prove lower bounds for temporal connectivity and shortest temporal path computation. We then study fastest temporal path computation, first proving several lower bounds and then presenting an algorithm that escapes these bounds by restricting the input to undirected edges and zero delays.

2 Preliminaries

We represent times with integers²²2This restriction does not weaken our lower bounds. Our upper bound algorithm easily generalizes to any representation of reals. and use Greek letters to name times. An interval of time $[\tau_{1},\tau_{2}]$ with $\tau_{1}\leq\tau_{2}$ represents all times $\tau$ satisfying $\tau_{1}\leq\tau\leq\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\leq\tau_{2}$ ( $\tau_{1}\leq\tau<\tau_{2}$ respectively).

An interval temporal graph, hereafter referred to simply as a temporal graph, is a pair $\mathcal{G}=(V,\mathcal{E})$ , where $V$ is a set of vertices and $\mathcal{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}\leq\tau_{2}$ and $\delta\geq 0$ that represent its beginning time, its ending time and its delay (or traveling time), respectively. Such a temporal edge represents the presence of edge $u v$ 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 $u v$ during interval $[\tau_{1},\tau_{2}]$ with delay $\delta$ . We let $tail(e)=u$ , $head(e)=v$ , $begin(e)=\tau_{1}$ , $end(e)=\tau_{2}$ , and $delay(e)=\delta$ denote its tail, its head, its beginning time, its ending time, and its delay respectively. When $\tau_{1}=\tau_{2}$ , the interval is reduced to a point, and then we refer to the point model. We often consider undirected temporal graphs where edges can be traversed in both directions. In that case, it is assumed that $\mathcal{E}$ is symmetric: for each $(u,v,\tau_{1},\tau_{2},\delta)\in\mathcal{E}$ , the symmetrical temporal edge $(v,u,\tau_{1},\tau_{2},\delta)$ is also in $\mathcal{E}$ . In other words, $\mathcal{G}$ is said to be undirected when $\mathcal{E}$ is symmetric. $\mathcal{G}$ is said to have uniform delay $\delta$ if all temporal edges have same delay $\delta$ .

The underlying graph of $\mathcal{G}$ is the (static) directed graph $G=(V,E)$ with same vertex set $V$ and edge set $E=\{{uv:\exists(u,v,\tau_{1},\tau_{2},\delta)\in\mathcal{E}}\}$ . Note that we let $u v$ denote the directed edge from $u$ to $v$ . We say that an edge $u v$ 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 $\mathcal{E}$ . When the temporal graph is undirected we also assume that the symmetrical edge is in $\mathcal{E}$ so that $\mathcal{E}$ is symmetric. When $\tau_{1}=\tau_{2}$ , we say that $u v$ is present at point $\tau_{1}$ with delay $\delta$ . Note that the underlying graph $G$ is directed. In contrast, when considering a (static) undirected graph $(V,E)$ with vertex set $V$ and edge set $E$ , we consider that $E\subseteq\binom{V}{2}$ is a set of unordered pairs, and we let $\{u,v\}$ denote an undirected edge between $u,v\in V$ .

When a temporal graph is clear from the context, we let $n=|V|$ denote its number of vertices, $M=|\mathcal{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 $\mathcal{E}$ . For simplicity, we assume that any vertex appears at least in one temporal edge so that we have $n=O(m)$ .

A temporal walk in $\mathcal{G}$ is a sequence of pairs $Q=(e_{1},\tau_{1}),\ldots,(e_{k},\tau_{k})$ where, for each $i\in[k]=\{{1,\ldots,k}\}$ , $e_{i}\in\mathcal{E}$ is a temporal edge and $\tau_{i}$ is a traversal time in the presence interval of $e_{i}$ , i.e. satisfying $begin(e_{i})\leq\tau_{i}\leq end(e_{i})$ . It is also required that $head(e_{i})=tail(e_{i+1})$ for all $i\in[k-1]$ , i.e., it induces a walk in the underlying graph $G$ , and that $\tau_{i}+delay(e_{i})\leq\tau_{i+1}$ for all $i\in[k-1]$ , i.e., 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 $s t$ -walk. We also say that $Q$ is a temporal walk departing from $s$ at time $\tau_{1}$ and arriving in $t$ at time $\tau_{k}+\delta_{k}$ where $\delta_{k}=delay(e_{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 said to be a loop when $tail(e_{1})=head(e_{k})$ . When all vertices $tail(e_{1}),head(e_{1}),\ldots,head(e_{k})$ are pairwise distinct, $Q$ is said to be a temporal path, or a temporal $s t$ -path if $s=tail(e_{1})$ and $head(e_{k})=t$ . Note that any temporal $s t$ -walk with $s\not=t$ can be transformed into a temporal $s t$ -path by removing sequences of temporal edges forming loops. A fastest temporal $s t$ -path is defined as a temporal $s t$ -path with minimum duration. A shortest temporal $s t$ -path is defined as a temporal $s t$ -path with minimum length. A foremost temporal $s t$ -path is defined as a temporal $s t$ -path with minimum arrival time. If there is a temporal $s t$ -path for every pair of vertices $s, t$ , $\mathcal{G}$ is temporally connected.

A walk $W$ in the underlying graph $G$ will be given as a sequence $v_{0},\ldots,v_{k}$ of vertices such that $v_{i-1}v_{i}$ is an edge for each $i\in[k]$ . It is said to be temporally feasible if there exists a sequence of times $\tau_{1}\leq\cdots\leq\tau_{k}$ such that each edge $v_{i-1}v_{i}$ is present at time $\tau_{i}$ with delay at most $\tau_{i+1}-\tau_{i}$ (using $\tau_{k+1}=\infty$ ). It is said to be a path when $v_{0},\ldots,v_{k}$ are pairwise distinct.

3 Lower bound for temporal connectivity

Recall that an interval temporal graph is temporally connected if it has a temporal $s t$ -path for every pair $s, t$ of vertices. Since computing the set of temporally reachable vertices from a given vertex can be done in linear time up to a logarithmic factor [16, 6], there is an $\widetilde{\cal O}(nM)$ -time algorithm for testing whether an interval temporal graph is temporally connected. We now state that this bound is tight under SETH, even in point temporal graphs.

Theorem 1.

Assuming SETH, for any $\varepsilon>0$ , there is no ${\cal O}((nM)^{1-\varepsilon})$ -time algorithm for testing whether a temporal graph is temporally connected, even if the temporal graph is an undirected point temporal graph with uniform delay zero (resp. one).

Proof.

Assuming SETH, for any $\epsilon>0$ , there is no $O(n^{2-\epsilon})$ -time algorithm distinguishing diameter $2$ from $3$ in graphs with $O(n)$ nodes and $O(n)$ edges [33]. To prove our result, it thus suffices to reduce Diameter-Two to Temporal-Connectivity, where the Diameter-Two problem asks whether a (static) undirected graph has diameter at most two, and the Temporal-Connectivity problem asks whether a temporal graph is temporally connected. For that, let $G=(V,E)$ be an arbitrary undirected graph with $O(n)$ nodes and $O(n)$ edges. Without loss of generality, $G$ is connected and has no self-loop. Let $F$ be the set of ordered pairs $(u,v)\in V^{2}$ such that $\{u,v\}\in E$ (thus $|F|=2|E|$ ). We construct from $G$ an undirected point temporal graph $\mathcal{H}_{G}$ as follows:

$\blacksquare$

The vertex set is $\{s\}\cup V\cup F_{1}\cup F_{2}$ where $F_{1},F_{2}$ are disjoint copies of $F$ and $s$ is an additional vertex. For every ordered pair $f=(u,v)\in F$ , we let $f_{1}\in F_{1},\ f_{2}\in F_{2}$ denote its copies. $F_{1}\cup F_{2}$ induces an independent set in the underlying graph of $\mathcal{H}_{G}$ and so does $\{s\}\cup V$ .
$\blacksquare$
For every ordered pair $f=(u,v)\in F$ , we add temporal edges with delay zero in $\mathcal{H}_{G}$ so that:
- –
  
  edge $uf_{1}$ is present at time $1$ (i.e. interval $[1,1]$ ),
- –
  
  edge $f_{1}v$ is present at time $2$ ,
- –
  
  edge $uf_{2}$ is present at time $3$ ,
- –
  
  edge $f_{2}v$ is present at time $4$ ,
- –
  
  edges $sf_{1}$ and $sf_{2}$ are present at times $0$ and $5$ .

We also add the corresponding symmetrical temporal edges so that $\mathcal{H}_{G}$ is undirected. All temporal edges of $\mathcal{H}_{G}$ have delay zero. See also Figure 1. Note that $\mathcal{H}_{G}$ has $O(n)$ vertices and $M=O(n)$ temporal edges as $G$ has $O(n)$ vertices and $O(n)$ edges.

Figure 1: Part of the point temporal graph

\mathcal{H}_{G}

induced by nodes

s,u,v,f_{1},f_{2}

for an ordered pair

f=(u,v)

such that

G

contains the undirected edge

\{u,v\}

. Each undirected edge

\{x,y\}

with label

\tau

in this Figure represents two point temporal edges with delay zero:

(x,y,\tau,\tau,0)

and

(y,x,\tau,\tau,0)

. Note that

\mathcal{H}_{G}

contains a similar structure with two other vertices

f_{1}^{\prime}\in F_{1}

and

f_{2}^{\prime}\in F_{2}

for the pair

(v,u)

.

Since $\{s\}\cup F_{1}\cup F_{2}$ induces a temporal graph, whose underlying graph is connected, and where all edges are present at time $0$ , vertices in $\{s\}\cup F_{1}\cup F_{2}$ can reach each other at time $0$ . Similarly, they can reach each other at time $5$ . Since there is a temporal edge between every vertex in $V$ and some vertex in $\{s\}\cup F_{1}\cup F_{2}$ at times $1$ and $4$ , this implies that $\mathcal{H}_{G}$ is temporally connected if and only if every pair of vertices in $V$ can temporally reach each other.

Let $u, v$ be two distinct vertices of $V$ . We will prove that there is a path of length at most $2$ from $u$ to $v$ in $G$ if and only if there is a temporal path from $u$ to $v$ in $\mathcal{H}_{G}$ . Let us first prove the direct implication. If $u, w, v$ is a path of length $2$ in $G$ , let $f=(u,w)$ and $g=(w,v)$ . Then $u,f_{1},w,g_{2},v$ is a path from $u$ to $v$ in the underlying graph of $\mathcal{H}_{G}$ which is temporally feasible in $\mathcal{H}_{G}$ by traversing edges $uf_{1},f_{1}w,wg_{2},g_{2}v$ at times $1,2,3,4$ , respectively.

Let us now prove the converse implication, and suppose that there is a temporal path $P$ from $u$ to $v$ in $\mathcal{H}_{G}$ . Since any edge incident to $u$ or $v$ is only present at times $1$ , $2$ , $3$ , or $4$ , $P$ only uses times $1$ , $2$ , $3$ , and $4$ . This implies that $P$ does not use $s$ , because it is only available at times $0$ or $5$ . Since the underlying graph of $\mathcal{H}_{G}$ is bipartite, with bipartition $(V\cup\{s\},F_{1}\cup F_{2})$ , and since any two edges $x f, f y$ incident to $f\in F_{1}\cup F_{2}$ , with $x\not=y$ , have distinct time availabilities, this implies that $P$ uses at most $3$ elements of $F_{1}\cup F_{2}$ , i.e., the underlying path of $P$ is either $u, f, v$ , or $u,f,w,f^{\prime},v$ , or $u,f,w,f^{\prime},x,f^{\prime\prime},v$ , with $w,x\in V$ and $f,f^{\prime},f^{\prime\prime}\in F_{1}\cup F_{2}$ . The latter case is indeed impossible. The distinct time availabilities of $u f$ and $f w$ imply that $f w$ is traversed at time $2$ at least. Hence, both $wf^{\prime}$ and $f^{\prime}x$ are traversed at time $2$ or later, implying $f^{\prime}\in F_{2}$ . Edges $wf^{\prime}$ and $f^{\prime}x$ are thus traversed at time $3$ and $4$ , respectively, in contradiction with the two distinct time availabilities of $xf^{\prime\prime}$ and $f^{\prime\prime}v$ . By construction, the two first cases imply that either $\{u,v\}\in E$ or that $\{u,w\},\{w,v\}\in E$ . Thus, there is a path of length at most $2$ between $u$ and $v$ in $G$ .

We thus conclude that $G$ has diameter at most $2$ if and only if $\mathcal{H}_{G}$ is temporally connected.

To obtain the result with uniform delay one, we modify the above construction so that all temporal edges have delay one and edges involving $s$ also appear at times $-1$ and $6$ . More precisely, we obtain $\mathcal{H}_{G}^{\prime}$ from $\mathcal{H}_{G}$ by changing all delays to one instead of zero and by adding edges $s f$ at times $-1$ and $6$ for all $f\in F_{1}\cup F_{2}$ (again with delay one and adding corresponding symmetrical temporal edges so that $\mathcal{H}_{G}^{\prime}$ is undirected).

Now, vertices in $\{s\}\cup F_{1}\cup F_{2}$ can reach each other at time 1 by passing through $s$ . They can also reach each other starting at time 5 and arriving at time 7. They can then reach any $v\in V$ at time 2. Similarly, any vertex $v$ can reach some $f\in F_{1}\cup F_{2}$ at time 2 and then any other $f^{\prime}\in\{s\}\cup F_{1}\cup F_{2}$ at time 7. This implies that $\mathcal{H}_{G}^{\prime}$ is temporally connected if and only if every pair of vertices in $V$ can temporally reach each other. The proof that this happens if and only if $G$ has diameter two is the same as above since the proof uses only strict temporal paths that also correspond to temporal paths in $\mathcal{H}_{G}^{\prime}$ . $\hfill\blacktriangleleft$

4 Lower bound for shortest temporal path

Theorem 2.

If, for every $\varepsilon>0$ , there is no combinatorial ${\cal O}(n^{3-\varepsilon})$ -time algorithm for detecting a triangle in an undirected graph, then for every $\epsilon^{\prime}>0$ , there is no combinatorial ${\cal O}((nM)^{1-\epsilon^{\prime}})$ -time algorithm for computing a shortest temporal $s t$ -path in a temporal graph, even if the temporal graph is undirected and has uniform delay zero (resp. one).

Proof.

Let $G=(V,E)$ be an instance of Triangle Detection that is a (static) undirected graph. Triangle detection consists in finding three pairwise distinct vertices $u, v, w$ such that the three undirected edges $\{u,v\},\{v,w\},\{w,u\}$ are in $E$ . Suppose $V=\{v_{1},\ldots,v_{n}\}$ . A temporal graph $\mathcal{H}_{G}$ is constructed as follows. Here, a permanent temporal edge between vertices $u$ and $v$ indicates that both edges $u v$ and $v u$ are present during the interval $[1,n]$ . All delays are zero.

$\blacksquare$

The vertex set of $\mathcal{H}_{G}$ consists of the vertices $s$ , $t$ , and $4$ disjoint copies of $V$ , denoted $V_{1},\ldots,V_{4}$ . For $j\in\{1,2,3,4\}$ and $i\in\{1,\ldots,n\}$ , let $v_{i}^{j}$ represent vertex $v_{i}$ in $V_{j}$ .
$\blacksquare$

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,\ldots,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}$ .
$\blacksquare$

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}$ (and their symmetric edges $v_{j}^{2}v_{i}^{1},v_{i}^{4}v_{j}^{3}$ ) are both present at time $i$ . Additionally, a permanent temporal edge between $v_{i}^{2}$ and $v_{j}^{3}$ is added.

Observe that $\mathcal{H}_{G}$ can be constructed in ${\cal 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.

$\vartriangleright$ Claim 0.

There is a triangle in $G$ if and only if there exists a temporal path in $\mathcal{H}_{G}$ from $s$ to $t$ using at most $n+4$ edges.

First, suppose that 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\leq i_{1}$ . Let $P_{1}$ denote this temporal path 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 $\mathcal{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 and traverses all of them at time $n\geq i_{1}$ . 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 2: A temporal path in

\mathcal{H}_{G}

corresponding to a triangle

v_{i_{1}},v_{i_{2}},v_{i_{3}}

in

G

, assuming that

G

has

n=5

vertices with

i_{1}=2,i_{2}=3,i_{3}=4

. Labels indicate when edges are traversed. Plain blue edges correspond to permanent temporal edges, i.e., they are present during interval

[1,n]

, while dashed red edges are present only at point

i_{1}

.

Now, suppose that there exists a temporal path $P$ from $s$ to $t$ of length at most $n+4$ . Let $P^{\prime}$ 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^{\prime}$ that is not within $V_{1}$ , and let $g$ be the last temporal edge of $P^{\prime}$ that is not within $V_{4}$ . By the structure of $\mathcal{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 the definition of temporal path, $g$ appears after (or at the same time as) $e$ in $P$ (possibly in a non-strict path they appear at the same time). Thus, $i_{1}\leq i_{4}$ . Now, observe that the distance from $s$ to $v_{i_{1}}^{1}$ in the underlying graph of $\mathcal{H}_{G}$ is $n-i_{1}+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 $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 $i_{4}\leq 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_{4}}^{4}=v_{i_{1}}^{4}$ must have the form $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}$ for some $i_{2},i_{3}\in[n]$ . By the way that $\mathcal{H}_{G}$ is constructed, $\{v_{i_{1}},v_{i_{2}}\},\{v_{i_{2}}v_{i_{3}}\}$ and $\{v_{i_{3}},v_{i_{1}}\}$ are undirected edges in $G$ , i.e., $v_{i_{1}},v_{i_{2}},v_{i_{3}}$ forms a triangle in $G$ . This concludes the proof for delay zero.

For delay one, the proof is very similar. We include it for the sake of completeness. To obtain an interval temporal graph $\mathcal{H}_{G}^{\prime}$ with uniform delay one, we modify the temporal edges of $\mathcal{H}_{G}$ as follows. All delays are set to one. All permanent edges are present during interval $[1,3n+3]$ instead of $[1,n]$ . For each undirected edge $\{v_{i},v_{j}\}\in E$ with $i<j$ , the symmetrical edges $v_{i}^{1}v_{j}^{2}$ and $v_{j}^{2}v_{i}^{1}$ are present at point $n+i$ while the symmetrical edges $v_{j}^{3}v_{i}^{4}$ and $v_{i}^{4}v_{j}^{3}$ are present at point $n+i+2$ . The proof similarly follows from the following claim.

$\vartriangleright$ Claim 0.

There is a triangle in $G$ if and only if there exists a temporal path in $\mathcal{H}_{G}^{\prime}$ from $s$ to $t$ using at most $n+4$ edges.

If $G$ contains a triangle $v_{i_{1}},v_{i_{2}},v_{i_{3}}$ with $i_{1}<i_{2}<i_{3}$ , we can again form a temporal path of length $n+4$ in $\mathcal{H}_{G}^{\prime}$ starting from $s$ at time $0$ , reaching $v_{i_{1}}^{1}$ within $V_{1}$ at time $n-i_{1}+1$ , waiting in $v_{i_{1}}^{1}$ until time $n+i_{1}$ following the temporal edges $e_{1}=(v_{i_{1}}^{1},v_{i_{2}}^{2},n+i_{1},n+i_{1}+1,1),e_{2}=(v_{i_{2}}^{2},v% _{i_{3}}^{3},n+i_{1}+1,n+i_{1}+2,1),e_{3}=(v_{i_{3}}^{3},v_{i_{1}}^{4},n+i_{1}% +2,n+i_{1}+3,1)$ at times $n+i_{1},n+i_{1}+1,n+i_{1}+2$ respectively, reaching $v_{i_{1}}^{4}$ at time $n+i_{1}+3$ , reaching $v_{1}^{4}$ within $V_{4}$ at time $n+2i_{1}+2$ , and arriving in $t$ at time $n+2i_{1}+3$ .

Conversely, suppose that $P$ is a temporal $s t$ -path in $\mathcal{H}_{G}^{\prime}$ of length at most $n+4$ . Its first temporal edge leading outside $V_{1}\cup\{s\}$ must be $e=(v_{i_{1}}^{1},v_{i_{2}}^{2},n+i_{1},n+i_{1},1)$ for some $i_{1}\in[n]$ . Its last temporal edge with a vertex outside $V_{4}\cup\{t\}$ must be $g=(v_{i_{3}}^{3},v_{i_{4}}^{4},n+i_{4}+2,i_{1},1)$ for some $i_{4}\in[n]$ . As the minimum length of path from $V_{2}$ to $V_{3}$ is one in the underlying graph of $\mathcal{H}_{G}^{\prime}$ , there is at least one temporal edge $f$ between $e$ and $g$ in $P$ . As $e$ and $g$ must be traversed at times $n+i_{1}$ and $n+i_{4}+2$ respectively, we get $n+i_{1}+2\leq n+i_{4}+2$ since $P$ is a temporal path and $e, f$ have delay one. We thus have $i_{1}\leq i_{4}$ . Again, the distance from $s$ to $v_{i_{1}}^{1}$ in the underlying graph of $\mathcal{H}_{G}^{\prime}$ is $n-i_{1}+1$ , the distance from $v_{i_{1}}^{1}$ to $v_{i_{4}}^{4}$ is at least 3, and the distance from $v_{i_{4}}$ to $t$ is $i_{4}$ . This implies that $P$ has length at least $n+4+(i_{4}-i_{1})\leq n+4$ . We thus have $i_{1}=i_{4}$ and $G$ contains the triangle $v_{i_{1}},v_{i_{2}},v_{i_{3}}$ . This concludes the proof for delay one. $\hfill\blacktriangleleft$

5 Complexity of fastest temporal path

5.1 Lower bounds for fastest temporal path

Theorem 3.

If, for every $\varepsilon>0$ , there is no ${\cal O}(n^{3-\varepsilon})$ -time algorithm for detecting a negative triangle in a weighted graph, then for every $\epsilon^{\prime}>0$ , there is no ${\cal O}((nM)^{1-\epsilon^{\prime}})$ -time algorithm for computing a fastest temporal $s t$ -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 undirected graph of a triangle whose total weight is negative. We now present an ${\cal 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 edge-weighted undirected graph with $n$ nodes and $m$ edges where $w:E\rightarrow\mathbb{Z}$ assigns a weight $w_{e}$ to each edge $e\in E$ . Without loss of generality, $V=\{0,1,2,\ldots,n-1\}$ and $G$ is loopless. Let $T=2n\max_{e\in E}|w_{e}|$ . We construct from $G$ an undirected temporal graph $\mathcal{H}_{G}$ as follows:

$\blacksquare$

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 respective copies. $V_{1},V_{2},V_{3}$ are independent sets.
$\blacksquare$

The underlying edge set includes $\{sv_{1},v_{3}t:v\in V\}\cup\{u_{1}v_{2},v_{1}u_{2},u_{2}v_{3},v_{2}u_{3}:\{u,% v\}\in E\}$ (and symmetrical edges).
$\blacksquare$

For every $\{u,v\}\in E$ , edges $u_{1}v_{2},v_{1}u_{2},u_{2}v_{3},v_{2}u_{3}$ and their symmetrical counterparts $v_{2}u_{1},u_{2}v_{1},v_{3}u_{2},u_{3}v_{2}$ are all present during $[0,2mT]$ with delay $T/2+w_{\{u,v\}}$ .
$\blacksquare$

Finally, let $E=\{e_{1},e_{2},\ldots,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, the symmetrical edges $su_{1},u_{1}s$ are both present at point $2(i-1)T$ with delay $T/2+w_{e_{i}}$ , and the symmetrical edges $v_{3}t,tv_{3}$ are both present during $[2(i-1)T,2iT]$ with delay $T/2$ .

Figure 3: Part of the underlying graph of

\mathcal{H}_{G}

corresponding to a triangle

u, v, x

contained in

G

assuming that the undirected edge

e_{i}\in E

is

\{u,v\}

with

u<v

. Recall that each undirected edge

\{y,z\}

of the figure corresponds to two symmetric edges

y z

and

z y

of

\mathcal{H}_{G}

. Here, the given labels indicate the delays of the corresponding temporal edges appearing during interval

[2(i-1)T,2iT)

. Plain blue edges are present during interval

[0,2mT]

. Dashed edges are more restricted: in particular, edges

su_{1}

and

u_{1}s

are present at point

2(i-1)T

, while edges

v_{3}t

and

tv_{3}

are present during interval

[2(i-1)T,2iT]

. Note that these edges can have other appearances depending on other neighbors of

u

and

v

in

G

.

Note that $\mathcal{H}_{G}$ has $3n+2$ vertices and $M=12m$ temporal edges (counting also symmetrical temporal edges), and the construction thus takes linear time. Figure 3 shows a schematic view of the resulting temporal graph.

We claim that there exists a temporal $s t$ -path in $\mathcal{H}_{G}$ with duration less than $2T$ if and only if $G$ contains a negative triangle. For that, let us fix a temporal $s t$ -path $P$ of minimum duration. By the construction of $\mathcal{H}_{G}$ , its first temporal edge is present at time $2(i-1)T$ for some $i\in[m]$ . Let $u, v$ be the endpoints of $e_{i}$ so that $P$ starts with edge $su_{1}$ , i.e. $e_{i}=\{u,v\}$ with $u<v$ . 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_{3}t$ . 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-k/n)T/2>(k-1)T/2$ while also being less than $2T$ . We thus have $k\leq 4$ . Furthermore, we must have $k=4$ since the distance between $s$ and $t$ is at least 4 in the underlying graph of $\mathcal{H}_{G}$ . In this situation, there must exist a vertex $x$ such that the underlying edges of $P$ are $su_{1},u_{1}x_{2},x_{2}v_{3},v_{3}t$ , implying that $u, x, v$ is a triangle of $G$ . As the temporal edges connecting $su_{1}$ and $v_{3}t$ have delays $T/2+w_{e_{i}}$ and $T/2$ respectively, the duration of $P$ is at least $2T+w_{e_{i}}+w_{\{u,x\}}+w_{\{x,v\}}$ , which is less than $2T$ if and only if the triangle $u, x, v$ is negative (see the corresponding path in Figure 3 for an illustration). Conversely, if $u, x, v$ 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$ -path that starts at time $0$ , has no waiting time, and has duration less than $2T$ . Therefore, the claim is proved. $\hfill\blacktriangleleft$

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

Theorem 4.

If, for every $\varepsilon>0$ , there is no combinatorial ${\cal O}(n^{3-\varepsilon})$ -time algorithm for detecting a triangle in an undirected graph, then for every $\epsilon^{\prime}>0$ , there is no combinatorial ${\cal O}((nM)^{1-\epsilon^{\prime}})$ -time algorithm for computing a fastest temporal path in a temporal graph, even if the temporal graph is undirected and has uniform delay one.

Due to space constraints, the proof can be found in the appendix of the related version. It also allows to state the following.

Theorem 5.

If, for every $\varepsilon>0$ , there is no combinatorial ${\cal O}(n^{3-\varepsilon})$ -time algorithm for detecting a triangle in an undirected graph, then for every $\varepsilon^{\prime}>0$ , there is no combinatorial ${\cal O}((nM)^{1-\varepsilon^{\prime}})$ -time algorithm for computing a fastest temporal path in a directed temporal graph with uniform delay zero.

5.2 Fastest temporal path in an undirected temporal graph with uniform delay zero

We obtain an algorithm for computing a fastest temporal path by solving the more complex profile problem. Given a temporal graph $\mathcal{G}$ and a pair of distinct vertices $s$ and $t$ in this graph, we define the $s t$ -profile $P\!F_{st}$ as the function $P\!F_{st}(\tau)$ associating each departure time $\tau$ from $s$ to the earliest arrival time in $t$ ; in other words, $P\!F_{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 $u v$ . The slope is one in intervals where the edge is present: for each temporal edge $(u,v,\tau_{1},\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 time is $\tau_{1}+\delta$ for $\tau<\tau_{1}$ if the next presence of $u v$ is during interval $[\tau_{1},\tau_{2}]$ with delay $\delta$ . Similarly, the profile function $f_{P}$ of a path $P=v_{1},\ldots,v_{k}$ can be obtained by composition of $E_{v_{1}v_{2}},\ldots,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, if $\cal P$ denotes the set of all paths from $s$ to $t$ in the underlying graph, we have $P\!F_{st}=\min_{P\in\cal P}f_{P}$ which is thus also a polyline with slopes in $\{{0,1}\}$ . See [14] 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\!F_{st}(\alpha_{i})$ and for every $\tau\in(\alpha_{i-1},\alpha_{i}]$ , we have $P\!F_{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 $s t$ -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 [14].

Theorem 6.

Given an undirected interval temporal graph $\mathcal{G}$ with no isolated vertices and $M$ temporal edges having all zero delay, and two vertices $s$ and $t$ , it is possible to compute in $\widetilde{\cal O}(M)$ time a fastest temporal path from $s$ to $t$ . Furthermore, a minimal representation of the $s t$ -profile $P\!F_{st}$ can be obtained with the same complexity.

To prove the above theorem, we propose a profile algorithm that, given the list of temporal edges of an interval temporal graph $\mathcal{G}=(V,\mathcal{E})$ and two distinct vertices $s,t\in V$ , computes a representation of the profile function $P\!F_{st}$ from $s$ to $t$ . The idea of the algorithm is to perform a time scan of the beginnings and ends of all temporal edges while maintaining connected components for edges present at each time $\tau$ considered. We also maintain for each connected component $c$ the last departure time $LDT[c]$ allowing us 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 beginning event (resp. ending event) which occurs when the edge begins at time $\tau_{1}$ (resp. ends at time $\tau_{2}$ ) and which is defined as the quintuple $(u,v,\tau_{1},\text{begin},\tau_{2})$ (resp. $(u,v,\tau_{2},\text{end},\tau_{2})$ ). As we consider an undirected temporal graph $\mathcal{G}$ , we generate only one beginning event and one ending event for each pair of symmetrical temporal edges. We assume that the temporal graph $\mathcal{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, beginning 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 $\mathcal{G}$ in $O(M\log M)$ time using sorting.

To maintain connected components as we scan edge events, we could use a dynamic connectivity algorithm [21, 17] (either fully dynamic or offline). However, we note that we can rely on the simpler dynamic tree algorithm of [32] (see also the Euler tour tree data-structure from [20]). The reason is that the ending times of edges are known in advance. We can thus maintain for each connected component a spanning tree consisting of edges with greatest ending times as we now explain. More precisely, we maintain a maximum-cost spanning tree of each connected component, where the cost of an edge is defined as the ending time of the corresponding temporal edge. Indeed, the data-structure of [32] maintains a collection of dynamic trees on a fixed set $V$ of vertices where each edge of a tree is associated to a cost. In particular, it allows to retrieve in logarithmic time the edge with minimum cost along the path from a node to the root of its tree. When adding an edge $\{u,v\}$ , if $u$ and $v$ are already in the same tree $T$ , we can thus find the edge $\{u^{\prime},v^{\prime}\}$ with smallest ending time along the cycle of $T\cup\{u,v\}$ and cut $T$ by deleting $\{u^{\prime},v^{\prime}\}$ before linking $u$ and $v$ (if $\{u^{\prime},v^{\prime}\}=\{u,v\}$ , we do nothing). If $u$ and $v$ are not in the same tree, we link the two trees according to [32]. We let $CC\_AddEdge(\{u,v\},\tau_{2})$ denote the resulting procedure for adding an edge $\{u,v\}$ with ending time $\tau_{2}$ . We let $CC\_RemoveEdge(\{u,v\})$ denote the procedure that cuts the tree containing $u$ and $v$ according to [32] if one vertex is parent of the other (and does nothing otherwise). We further let $CC(u)$ denote the procedure that returns the ID of the root of the tree containing $u$ according to [32]. We use this ID (a number between 1 and $n$ ) to identify the component spanned by the tree, so that the expression $CC(u)=CC(v)$ allows us to test whether $u$ and $v$ are in the same connected component. All these procedures can be implemented in $O(\log n)$ time [32]. Note that the simpler version in amortized $O(\log n)$ time suffices for our purposes. We let $CC\_Init(V)$ denote the procedure that creates $n$ single-node trees, one for each vertex in $V$ (in linear time). Processing the event list in order, we can thus update the dynamic trees representing the connected components of the graph of edges present at the time of each event.

Algorithm 1 One-to-one profile.

The update of last departure times is then rather simple. When two components merge because of the appearance of an edge $u v$ 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 $u v$ at time $\tau$ , the two new components get same last departure time as the component before splitting since temporal paths reaching that component arrive at time $\tau$ or before, and waiting is then possible. 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\!F_{st}(\lambda)\leq\tau$ . We will prove that when a higher value of $\lambda$ is observed for $t$ , $\tau$ corresponds to the earliest arrival time when departing at $\lambda$ and we then have $P\!F_{st}(\lambda)=\tau$ . Note that $\tau-\lambda$ is then the duration of the corresponding temporal path from $s$ to $t$ . Each time an event affects the connected component of the target $t$ , we update a list $P r o f$ of triples accordingly so that it represents the profile $P\!F_{st}$ up to that event. See the pseudo-code of Algorithm 1 for more details.

Proposition 7.

Given an undirected interval temporal graph $G$ with with no isolated vertices and $M$ temporal edges having all zero delay, and two vertices $s$ and $t$ , Algorithm 1 computes a representation of the $s t$ -profile in $O(M\log M)$ time.

First note that Theorem 6 easily follows from Proposition 7 since the duration of a fastest temporal $s t$ -path as well as the starting time $\lambda$ of such a fastest temporal path can easily be obtained by scanning the $s t$ -profile in $O(M)$ time to obtain the triple $(\lambda,\tau,s)$ minimizing $\tau-\lambda$ . We can then find a fastest temporal $s t$ -path departing at time $\lambda$ by computing an earliest-arrival $s t$ -path departing at time $\lambda$ in $O(M\log M)$ time. Indeed, after an $O(M\log M)$ -time preprocessing for obtaining for each underlying edge $u v$ the sorted list of temporal edges connecting $u v$ , we can compute such a temporal path through a temporal version of Dijkstra’s algorithm [16, 6] 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 $u v$ that can be traversed at a certain time $\tau$ for a given neighbor $v$ (in the underlying graph) of a node $u$ reached at time $\tau$ . The preprocessing also includes removing the overlaps between the temporal edges corresponding to various appearances of the same edge, see [24] for more details. As we assume that there is no isolated vertex, we have $n=O(m)=O(M)$ and $\log n=O(\log M)$ . As a final remark, a minimal representation of the profile can easily be obtained from the computed one through a linear-time post-processing scan where we merge two consecutive triples if they correspond to the same line. Due to space constraints, the proof of Proposition 7 can be found in the Appendix of the related version.

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 (resp. shortest) 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 $s t$ -path and the $\widetilde{\cal O}(mM)=\widetilde{\cal O}(n^{2}M)$ upper bound given by the best-known algorithm [14]. Note that the gap can be large for dense underlying graphs with $m=\Theta(n^{2})$ .

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 $\widetilde{\cal 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 $\widetilde{\cal O}(nM)$ -time algorithm for one-to-all profiles. Besides combinatorial algorithms, do faster algorithms for shortest temporal path or fastest temporal path with uniform delay one exist (e.g. leveraging linear algebra)?

Testing temporal connectivity might be related to the existence of a specific temporal spanner, that is a subset of temporal edges which are sufficient to preserve temporal connectivity. Note that our reduction for proving Theorem 1 produces a sparse temporal graph with $O(n)$ temporal edges, implying that the existence of a sparse spanner is not enough to enable temporal connectivity testing in subquadratic time. We ask whether subquadratic time could be enabled by the existence of a specific well-structured temporal spanner. For example, a pivot vertex [10], which is a vertex that all vertices can reach by some time $\tau$ and which can reach all other vertices after $\tau$ , enables such a temporal spanner. We ask whether such a pivot and an appropriate time $\tau$ can be found in subquadratic time when they exist.

References

[1] Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory Comput. Syst., 61(3):907–944, 2017. doi:10.1007/S00224-017-9757-X.
[2] 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.
[3] Eleni C. Akrida and Paul G. Spirakis. On verifying and maintaining connectivity of interval temporal networks. Parallel Process. Lett., 29(2):1950009:1–1950009:16, 2019. doi:10.1142/S0129626419500099.
[4] Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Samuel Pierre, Michel Barbeau, and Evangelos Kranakis, editors, Ad-Hoc, Mobile, and Wireless Networks, Second International Conference, ADHOC-NOW 2003 Montreal, Canada, October 8-10, 2003, Proceedings, volume 2865 of Lecture Notes in Computer Science, pages 259–270. Springer, 2003. doi:10.1007/978-3-540-39611-6_23.
[5] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot. On computing pareto optimal paths in weighted time-dependent networks. Inf. Process. Lett., 168:106086, 2021. doi:10.1016/J.IPL.2020.106086.
[6] 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.
[7] Benjamin Merlin Bumpus and Kitty Meeks. Edge Exploration of Temporal Graphs. Algorithmica, 85(3):688–716, 2022. doi:10.1007/s00453-022-01018-7.
[8] 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.
[9] 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. doi:10.4230/LIPIcs.ICALP.2019.134.
[10] Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. J. Comput. Syst. Sci., 121:1–17, 2021. doi:10.1016/J.JCSS.2021.04.004.
[11] Justine Cauvi and Laurent Viennot. Parameterized restless temporal path. In Artur Jez and Jan Otop, editors, Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings, volume 16106 of Lecture Notes in Computer Science, pages 82–93. Springer, 2025. doi:10.1007/978-3-032-04700-7_7.
[12] 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. doi:10.1016/0022-247X(66)90009-6.
[13] Isnard Lopes Costa, Raul Lopes, Andrea Marino, and Ana Silva. On computing large temporal (unilateral) connected components. J. Comput. Syst. Sci., 144:103548, 2024. doi:10.1016/J.JCSS.2024.103548.
[14] 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. doi:10.1007/S00453-010-9461-6.
[15] Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection scan algorithm. ACM J. Exp. Algorithmics, 23, 2018. doi:10.1145/3274661.
[16] Stuart E. Dreyfus. An appraisal of some shortest-path algorithms. Oper. Res., 17(3):395–412, 1969. doi:10.1287/OPRE.17.3.395.
[17] David Eppstein. Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms, 17(2):237–250, 1994. doi:10.1006/JAGM.1994.1033.
[18] Luca Foschini, John Hershberger, and Subhash Suri. On the complexity of time-dependent shortest paths. Algorithmica, 68(4):1075–1097, 2014. doi:10.1007/S00453-012-9714-7.
[19] 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.
[20] 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.
[21] 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.
[22] Petter Holme. Modern temporal network theory: A colloquium. CoRR, abs/1508.01303, 2015. arXiv:1508.01303.
[23] Petter Holme and Jari Saramäki. Temporal networks. Physics Reports, 519(3):97–125, 2012. Temporal Networks. doi:10.1016/j.physrep.2012.03.001.
[24] 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. doi:10.1007/S41109-022-00499-3.
[25] 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.
[26] 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. doi:10.1007/S13278-018-0537-7.
[27] 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. doi:10.1016/J.JCSS.2023.04.005.
[28] Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math., 12(4):239–280, 2016. doi:10.1080/15427951.2016.1177801.
[29] 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.
[30] Léo Rannou, Clémence Magnien, and Matthieu Latapy. Strongly connected components in stream graphs: Computation and experimentations. In Rosa M. Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis Mateus Rocha, and Marta Sales-Pardo, editors, Complex Networks & Their Applications IX - Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2020, 1-3 December 2020, Madrid, Spain, volume 943 of Studies in Computational Intelligence, pages 568–580. Springer, 2020. doi:10.1007/978-3-030-65347-7_47.
[31] Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 515–524. ACM, 2013. doi:10.1145/2488608.2488673.
[32] Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362–391, 1983. doi:10.1016/0022-0000(83)90006-5.
[33] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity, pages 3447–3487. World Scientific Publishing Co Pte Ltd, 2018. doi:10.1142/9789813272880_0188.
[34] 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.
[35] 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.

Appendix A Lower bounds for fastest temporal path with uniform delay one or zero

Proof of Theorem 4.

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

$\blacksquare$

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.
$\blacksquare$

The underlying edge set includes $\{sv_{1},v_{3}t:v\in V\}\cup\{u_{1}v_{2},u_{2}v_{3}:\{u,v\}\in E\}$ (and symmetrical edges).
$\blacksquare$

For every $\{u,v\}\in E$ , edges $u_{1}v_{2},u_{2}v_{3}$ and their symmetrical counterparts $v_{2}u_{1},v_{3}u_{2}$ are all present during $[0,n\cdot N+3]$ .
$\blacksquare$

For every $v\in V$ , the symmetrical edges $sv_{1},v_{1}s$ are both present at point $v\cdot N$ , while the symmetrical edges $v_{3}t,tv_{3}$ are both present at point $u\cdot N+3$ for each $u\in N(v)$ .
$\blacksquare$

Finally, all temporal edges have delay one.

Note that we can construct $\mathcal{G}$ from $G$ in ${\cal 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 $u, v, w$ is a triangle of $G$ , then there exists a temporal path starting at time $u\cdot N$ , 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$ ). The underlying path of $P$ must thus be $s,u_{1},v_{2},w_{3},t$ for some triple $u,v,w\in V$ satisfying $\{u,v\},\{v,w\}\in E$ . This path has $su_{1}$ and $w_{3}t$ as first and last edges respectively. Then, the starting time of $P$ must be $u\cdot N$ and edge $w_{3}t$ must be present at time $u\cdot N+3$ which happens only when $u\in N(w)$ . Since $G$ is loopless, $u, v, w$ are pairwise distinct. Therefore, $G$ contains the triangle $u, v, w$ . This proves the claim. $\hfill\blacktriangleleft$

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 $\mathcal{H^{\prime}}$ 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 $\mathcal{H^{\prime}}$ contains a temporal $s t$ -path of duration 3 if and only if $G$ contains a triangle. The proof of Theorem 5 is almost identical to that of Theorem 4 and is omitted.

Appendix B Profile computation in undirected temporal graphs with uniform delay zero

Proof of Proposition 7.

Considering all events up to an event $e\in\mathcal{E}$ , let $\mathcal{H^{\prime}}$ be the temporal graph with the same set of vertices as $\mathcal{G}$ and all temporal edges $(u,v,\tau_{1},\tau_{2})$ of $\mathcal{G}$ such that the event $(u,v,\tau_{1},\text{begin},\tau_{2})$ is not after $e$ in the event list $\mathcal{E}$ . The temporal edges of $\mathcal{G}^{e}$ whose ending events come after $e$ in $\mathcal{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. 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 a temporal $s w$ -walk departing at time $\lambda$ in $G^{e}$ and arriving no later than $\tau^{e}$ . Similarly, we use $CC^{e}$ , $LDT^{e}$ and $Prof^{e}$ to refer to the values stored in $C C$ , $L D T$ and $P r o f$ respectively after the algorithm has processed the event $e$ . We aim at proving the following claim.

$\vartriangleright$ Claim 8.

For each event $e$ , we have $LDT^{e}[CC^{e}(w)]=\lambda^{e}(w)$ .

We first note that this claim allows us to prove that Algorithm 1 correctly identifies a triple $(\lambda,\tau,s)$ corresponding to a fastest temporal $s t$ -path with duration $\tau-\lambda$ . Consider a fastest temporal $s t$ -path $P^{*}$ and let $\lambda^{*}$ and $\tau^{*}$ denote its departure time from $s$ and arrival time in $t$ respectively. Among the suffixes of $P^{*}$ with temporal edges present at time $\tau^{*}$ , consider the last beginning event $e$ of one of these temporal edges and consider its time $\tau^{e}\leq\tau^{*}$ . As $\tau^{e}<\tau^{*}$ would lead to a faster temporal $s t$ -path, we must have $\tau^{e}=\tau^{*}$ . As the suffix from the temporal edge associated to $e$ is present at time $\tau^{e}$ by the choice of $e$ and $t$ is in the connected component of the suffix when processing $e$ , the claim implies $LDT^{e}[CC^{e}(t)]=\lambda^{e}(t)$ and $\lambda^{e}(t)=\lambda^{*}$ by definitions of $\lambda^{e}(t)$ and $P^{*}$ . If $\lambda^{*}>\lambda_{t}$ , the triplet $(\lambda^{*},\tau^{*},0)$ is added to the profile at Line 13. Otherwise, a triplet $(\lambda_{t},\tau^{\prime},s)$ was added previously with $\lambda^{*}\leq\lambda_{t}$ and $\tau^{\prime}\leq\tau^{*}$ , implying $\tau^{\prime}-\lambda_{t}\leq\tau^{*}-\lambda^{*}$ . As $P^{*}$ is a fastest temporal path, we must have $\tau^{\prime}-\lambda_{t}=\tau^{*}-\lambda^{*}$ . In both cases, Algorithm 1 correctly identifies a triple $(\lambda,\tau,s)$ corresponding to a fastest temporal $s t$ -path. Additionally, Claim 8 also implies that each triple $(\lambda,\tau,0)$ added to $P r o f$ corresponds to a temporal path starting from $s$ at time $\lambda$ and arriving in $t$ at time $\tau$ . Moreover, a triple $(\tau,\tau,1)$ is added to $P r o f$ only if $s$ and $t$ are in the same connected component at time $\tau$ . We can thus conclude that the minimum $\tau-\lambda$ over all triples $(\lambda,\tau,s)$ of $P r o f$ is the duration of a fastest temporal $s t$ -path.

Proof of Claim 8. We prove Claim 8 by induction on the number of events processed. It relies mainly 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 edges that are present in $\mathcal{G}$ at time $\tau^{e}$ and whose ending events are after $e$ in $\mathcal{E}$ . The ordering of $\mathcal{E}$ , with all beginning 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 $\mathcal{G}^{e}$ . In particular, when two vertices $u$ and $v$ are in the same connected component (i.e. $CC^{e}(u)=CC^{e}(v)$ ), they are connected through unclosed temporal edges of $\mathcal{G}^{e}$ . Note that this implies the existence of an instantaneous temporal $u v$ -path that uses only unclosed temporal edges which are all traversed at the same time $\tau^{e}$ .

Initially, we consider an empty temporal graph $\mathcal{G}^{0}$ and the claim is clearly satisfied for any vertex $w\not=s$ . Now, suppose that Claim 8 is satisfied for any vertex $w\not=s$ before scanning an event $f$ at time $\tau=\tau^{f}$ . Note that the algorithm first sets $LDT[CC(s)]:=\tau$ , so that the claim $LDT^{f}[CC^{f}(w)]=\lambda^{f}(w)$ is satisfied for $w=s$ and all vertices $w$ in $CC^{f}(s)$ . Now consider any vertex $w$ outside of $CC^{f}(s)$ . In that case, any temporal $s w$ -path uses some temporal edge ending before $\tau^{f}$ , implying $\lambda^{f}(w)\leq\tau^{e}$ where $e$ denotes the event preceding $f$ (we use $e=0$ and $\tau^{e}=-\infty$ if $f$ is the first event). We distinguish two cases.

Ending event case. If $f$ corresponds to the disappearance of an edge $u v$ , we have $\mathcal{G}^{f}=\mathcal{G}^{e}$ , implying $\lambda^{f}(w)\geq\lambda^{e}(w)$ . As we have $\lambda^{f}(w)\leq\tau^{e}$ (since $w$ is outside of $CC^{f}(s)$ ), the corresponding temporal $s w$ -path exists in $G^{e}$ and we have $\lambda^{f}(w)=\lambda^{e}(w)$ . The updates in that case ensure that $LDT[CC(w)]$ keeps the same value (after the possible change of $CC(w)$ ) so that $LDT^{f}[CC^{f}(w)]=\lambda^{e}(w)=\lambda^{f}(w)$ still holds.

Beginning event case. If $f$ corresponds to the appearance of an edge $u v$ , $\mathcal{G}^{f}$ differs from $\mathcal{G}^{e}$ by the addition of the two temporal edges $f^{\prime}=(u,v,\tau^{f},\tau_{2})$ and $f^{\prime\prime}=(v,u,\tau^{f},\tau_{2})$ associated to $f$ . We thus have $\lambda^{f}(w)\geq\lambda^{e}(w)$ , and $\lambda^{f}(w)>\lambda^{e}(w)$ can only occur if any temporal $s w$ -path with departure time $\lambda^{f}(w)$ uses $f^{\prime}$ or $f^{\prime\prime}$ . Consider such a temporal $s w$ -path departing at time $\lambda^{f}(w)$ and assume without loss of generality that it traverses $f^{\prime}$ from $u$ to $v$ , implying $\lambda^{f}(w)\leq\lambda^{e}(u)$ by definition of $\lambda^{e}(u)$ . As we set $LDT[CC(w)]$ to $\max\{{LDT[CC(u)],LDT[CC(v)]}\}$ in that case, we then have $LDT^{f}[CC^{f}(w)]\geq LDT^{e}[CC^{e}(u)]=\lambda^{e}(w)$ by induction hypothesis. Combining this with the previous inequality, we get $LDT^{f}[CC^{f}(w)]\geq\lambda^{f}(w)$ . We also have $\lambda^{f}(w)\geq LDT^{f}[CC^{f}(w)]$ since the induction hypothesis implies the existence of a temporal $s x$ -path $P$ to a node $x$ in $\{u,v\}$ departing at $\max\{{LDT^{e}[CC^{e}(u)],LDT^{e}[CC^{e}(v)]}\}=LDT^{f}[CC^{f}(w)]$ and arriving at $\tau^{e}$ or before such that $P$ can be extended by an instantaneous temporal $x w$ -path at time $\tau^{f}\geq\tau^{e}$ . We thus finally get $LDT^{f}[CC^{f}(w)]=\lambda^{f}(w)$ in that case too. Claim 8 thus follows by induction.

We now turn to the proof of the profile computation. We denote by $P\!F_{st}^{e}$ the $s t$ -profile in $\mathcal{G}^{e}$ up to $\tau^{e}$ (i.e. with support restricted to $(-\infty,\tau^{e}]$ ) and let $last(P\!F_{st}^{e})$ denote the maximum time $\tau\leq\tau^{e}$ for which $P\!F_{st}^{e}(\tau)$ is defined (by convention $last(P\!F_{st}^{e})=-\infty$ when $\mathcal{G}^{e}$ does not contain any temporal path from $s$ to $t$ ). We aim at proving the following claim.

$\vartriangleright$ Claim 9.

For each event $e$ , $Prof^{e}$ is a representation of $P\!F_{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 $s t$ -profile in $\mathcal{G}=\mathcal{G}^{l}$ . The complexity of the algorithm directly follows from the time complexities of the dynamic connected component procedures. Proposition 7 will thus follow from the proof of this claim.

We first state the following about profile inclusion.

$\vartriangleright$ Claim 10.

For any two events $e$ and $f$ such that $e$ precedes $f$ in $\mathcal{E}$ , and any time $\lambda\leq last(P\!F_{st}^{e})$ , we have $P\!F_{st}^{f}(\lambda)=P\!F_{st}^{e}(\lambda)$ .

Since any temporal path in $\mathcal{G}^{e}$ is also a temporal path in $\mathcal{G}^{f}$ , we obtain $P\!F_{st}^{f}(\lambda)\leq P\!F_{st}^{e}(\lambda)$ for any time $\lambda\leq last(P\!F_{st}^{e})$ . We also have $P\!F_{st}^{e}(\lambda)\leq\tau^{e}$ since a temporal path arriving after $\tau^{e}$ in $\mathcal{G}^{e}$ uses only unclosed temporal edges after $\tau^{e}$ , and since these edges begin 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\leq last(P\!F_{st}^{e})$ since no temporal path in $\mathcal{G}^{f}$ can arrive before $P\!F_{st}^{e}(\lambda)\leq\tau^{e}$ as the possible additional temporal edges of $\mathcal{G}^{f}$ begin at $\tau^{e}$ or later.

We now prove Claim 9 by induction on the number of events processed. Initially, we consider an empty temporal graph $\mathcal{G}^{0}=(V,\emptyset)$ (with no temporal edge). As expected, $P r o f$ is empty reflecting that there exists no temporal walk from $s$ to $t$ in $\mathcal{G}^{0}$ . We assume the induction hypothesis for event $e$ , i.e. $Prof^{e}$ is a representation of $P\!F_{st}^{e}$ . Let us consider the next event $f$ and distinguish two cases.

Ending event case. First suppose that $f$ is an ending event $(u,v,\tau^{f},\text{end},\tau^{f})$ . Note that we have $\mathcal{G}^{f}=\mathcal{G}^{e}$ by definition. By Claim 10, we have $P\!F_{st}^{f}(\lambda)=P\!F_{st}^{e}(\lambda)$ for $\lambda\leq last(P\!F_{st}^{e})$ so that $Prof^{e}$ is a valid representation of $P\!F_{st}^{f}(\lambda)$ for $\lambda\leq\tau^{e}$ . Moreover, if $\lambda^{f}(t)\leq\tau^{e}$ , $G^{e}=G^{f}$ implies $\lambda^{f}(t)=\lambda^{e}(t)\leq last(P\!F_{st}^{e})$ and we have $P\!F_{st}^{f}=P\!F_{st}^{e}$ . The only case when $P\!F_{st}^{f}$ differs from $P\!F_{st}^{e}$ is thus when $\lambda^{f}(t)>\tau^{e}$ , that is when there exists a temporal $s t$ -path composed of unclosed temporal edges. In other words, this occurs when $CC^{e}(t)=CC^{e}(s)$ and $st\_connected$ is true. This implies that we then have $last(P\!F_{st}^{e})=\tau^{e}$ and $P\!F_{st}^{e}(\tau^{e})=\tau^{e}$ . Moreover, $P\!F_{st}^{f}$ is then the identity over $[\tau^{e},\tau^{f}]$ as reflected by the addition of the triple $(\tau^{f},\tau^{f},1)$ at the end of $P r o f$ in that case at Line 20. $Prof^{f}$ is thus a valid representation of $P\!F_{st}^{f}$ .

Beginning event case. Now suppose that $f$ is a beginning event $(u,v,\tau^{f},\text{begin},\tau_{2})$ for the temporal edge $f^{\prime}=(u,v,\tau^{f},\tau_{2})$ of $G$ . Note that $\mathcal{G}^{f}$ then differs from $\mathcal{G}^{e}$ by having the two extra temporal edges $f^{\prime}$ and its symmetrical temporal edge $f^{\prime\prime}=(v,u,\tau^{f},\tau_{2})$ . Consider the $s t$ -profile $P\!F_{st}^{f}$ in $G^{f}$ . It 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 $P r o f$ at Line 20 in that case. Note that we then have $last(P\!F_{st}^{e})=\tau^{e}$ and $P\!F_{st}^{e}(\tau^{e})=\tau^{e}$ .

Now consider the case when $t$ is connected to $u$ or $v$ , we have $\lambda_{t}=LDT^{e}[CC^{e}(t)]=\lambda^{e}(t)$ and $\lambda^{f}(t)=LDT^{f}[CC^{f}(u)]=\lambda$ by Claim 8. If $\lambda>\lambda_{t}$ , this is in correspondence with the addition of $(\lambda,\tau^{f},0)$ at Line 13 as a temporal $s t$ -path departing at time $\lambda$ must use $f^{\prime}$ or $f^{\prime\prime}$ 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\leq\lambda_{t}$ can only occur when $\lambda=\lambda_{t}=\lambda^{f}(t)=\lambda^{e}(t)$ since we have $\lambda^{f}(t)\geq\lambda^{e}(t)$ as any temporal path in $\mathcal{G}^{e}$ is also a temporal path in $\mathcal{G}^{f}$ . We then have $\lambda^{f}(t)=last(P\!F_{st}^{e})$ implying $P\!F_{st}^{f}=P\!F_{st}^{e}$ which justifies to not modify $P r o f$ in that case.

Finally consider the case when $t$ is not in the connected component of neither $s$ , nor $u$ , nor $v$ . We then have $P\!F_{st}^{f}=P\!F_{st}^{e}$ since a temporal $s t$ -path in $\mathcal{G}^{f}$ cannot traverse $f^{\prime}$ or $f^{\prime\prime}$ as they appear too late to reach $t$ after $\tau^{f}$ . Any temporal $s t$ -path in $G^{f}$ is thus also a temporal $s t$ -path in $\mathcal{G}^{e}$ with same departure time. This is indeed reflected by the fact that $P r o f$ is not modified in that case, yielding to $Prof^{f}=Prof^{e}$ . We finally obtain that $Prof^{f}$ is a valid representation of $P\!F_{st}^{f}$ in all cases. This concludes our proof of Claim 9 as well as the correctness of Algorithm 1. Its time complexity directly derives from that of sorting edge events and the amortized $O(\log n)=O(\log M)$ time complexity of the dynamic tree operations that allow to maintain connected components as explained in Section 5.2. This ends the proof of Proposition 7 and its direct consequence Theorem 6. $\hfill\blacktriangleleft$

[bib.bib1] [1] Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory Comput. Syst., 61(3):907–944, 2017. doi:10.1007/S00224-017-9757-X.

[bib.bib2] [2] 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.

[bib.bib3] [3] Eleni C. Akrida and Paul G. Spirakis. On verifying and maintaining connectivity of interval temporal networks. Parallel Process. Lett., 29(2):1950009:1–1950009:16, 2019. doi:10.1142/S0129626419500099.

[bib.bib4] [4] Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Samuel Pierre, Michel Barbeau, and Evangelos Kranakis, editors, Ad-Hoc, Mobile, and Wireless Networks, Second International Conference, ADHOC-NOW 2003 Montreal, Canada, October 8-10, 2003, Proceedings, volume 2865 of Lecture Notes in Computer Science, pages 259–270. Springer, 2003. doi:10.1007/978-3-540-39611-6_23.

[bib.bib5] [5] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot. On computing pareto optimal paths in weighted time-dependent networks. Inf. Process. Lett., 168:106086, 2021. doi:10.1016/J.IPL.2020.106086.

[bib.bib6] [6] 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.

[bib.bib7] [7] Benjamin Merlin Bumpus and Kitty Meeks. Edge Exploration of Temporal Graphs. Algorithmica, 85(3):688–716, 2022. doi:10.1007/s00453-022-01018-7.

[bib.bib8] [8] 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.

[bib.bib9] [9] 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. doi:10.4230/LIPIcs.ICALP.2019.134.

[bib.bib10] [10] Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. J. Comput. Syst. Sci., 121:1–17, 2021. doi:10.1016/J.JCSS.2021.04.004.

[bib.bib11] [11] Justine Cauvi and Laurent Viennot. Parameterized restless temporal path. In Artur Jez and Jan Otop, editors, Fundamentals of Computation Theory - 25th International Symposium, FCT 2025, Wrocław, Poland, September 15-17, 2025, Proceedings, volume 16106 of Lecture Notes in Computer Science, pages 82–93. Springer, 2025. doi:10.1007/978-3-032-04700-7_7.

[bib.bib12] [12] 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. doi:10.1016/0022-247X(66)90009-6.

[bib.bib13] [13] Isnard Lopes Costa, Raul Lopes, Andrea Marino, and Ana Silva. On computing large temporal (unilateral) connected components. J. Comput. Syst. Sci., 144:103548, 2024. doi:10.1016/J.JCSS.2024.103548.

[bib.bib14] [14] 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. doi:10.1007/S00453-010-9461-6.

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

[bib.bib16] [16] Stuart E. Dreyfus. An appraisal of some shortest-path algorithms. Oper. Res., 17(3):395–412, 1969. doi:10.1287/OPRE.17.3.395.

[bib.bib17] [17] David Eppstein. Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms, 17(2):237–250, 1994. doi:10.1006/JAGM.1994.1033.

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

[bib.bib19] [19] 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.

[bib.bib20] [20] 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.

[bib.bib21] [21] 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.

[bib.bib22] [22] Petter Holme. Modern temporal network theory: A colloquium. CoRR, abs/1508.01303, 2015. arXiv:1508.01303.

[bib.bib23] [23] Petter Holme and Jari Saramäki. Temporal networks. Physics Reports, 519(3):97–125, 2012. Temporal Networks. doi:10.1016/j.physrep.2012.03.001.

[bib.bib24] [24] 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. doi:10.1007/S41109-022-00499-3.

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

[bib.bib26] [26] 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. doi:10.1007/S13278-018-0537-7.

[bib.bib27] [27] 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. doi:10.1016/J.JCSS.2023.04.005.

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

[bib.bib29] [29] 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.bib30] [30] Léo Rannou, Clémence Magnien, and Matthieu Latapy. Strongly connected components in stream graphs: Computation and experimentations. In Rosa M. Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis Mateus Rocha, and Marta Sales-Pardo, editors, Complex Networks & Their Applications IX - Volume 1, Proceedings of the Ninth International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2020, 1-3 December 2020, Madrid, Spain, volume 943 of Studies in Computational Intelligence, pages 568–580. Springer, 2020. doi:10.1007/978-3-030-65347-7_47.

[bib.bib31] [31] Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 515–524. ACM, 2013. doi:10.1145/2488608.2488673.

[bib.bib32] [32] Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362–391, 1983. doi:10.1016/0022-0000(83)90006-5.

[bib.bib33] [33] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity, pages 3447–3487. World Scientific Publishing Co Pte Ltd, 2018. doi:10.1142/9789813272880_0188.

[bib.bib34] [34] 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.

[bib.bib35] [35] 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.

Complexity Gaps Between Point and Interval Temporal Graphs for Some Reachability Problems

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our contribution

More related work.

Structure of the paper

2 Preliminaries

3 Lower bound for temporal connectivity

Theorem 1.

Proof.

4 Lower bound for shortest temporal path

Theorem 2.

Proof.

⊳ Claim 0.

⊳ Claim 0.

5 Complexity of fastest temporal path

5.1 Lower bounds for fastest temporal path

Theorem 3.

Proof.

Theorem 4.

Theorem 5.

5.2 Fastest temporal path in an undirected temporal graph with uniform delay zero

Theorem 6.

Proposition 7.

6 Conclusion

References

Appendix A Lower bounds for fastest temporal path with uniform delay one or zero

Proof of Theorem 4.

Appendix B Profile computation in undirected temporal graphs with uniform delay zero

Proof of Proposition 7.

⊳ Claim 8.

⊳ Claim 9.

⊳ Claim 10.

$\vartriangleright$ Claim 0.

$\vartriangleright$ Claim 0.

$\vartriangleright$ Claim 8.

$\vartriangleright$ Claim 9.

$\vartriangleright$ Claim 10.