“Space and time emerged together and are inseparable.”

In static graphs, reachability describes movement through the space of the graph; which nodes can be reached via available edges. In temporal graphs, we move through both space and time: edges are not always available and reachability depends on when a connection can be used, not just whether it exists.

The definition of temporal reachability depends on the notion of a temporal trip: Temporal Paths/Trips/Journeys

<aside> 💡

Definition.

A temporal path is a sequence of temporal edges $(e_i,t_i){i\in[\ell]}$ where $(e_i){i\in[\ell]}$ forms a path in the footprint $G$, and the time labels $(t_i)_{i\in[\ell]}$ are non-decreasing. A vertex $u$ (temporally) reaches vertex $v$ iff there exists a temporal path from $v$ to $u$.

</aside>

Variants of temporal reachability

• Directed vs Undirected: whether the edges of the footprint $G$ are directed or undirected

• Strict vs Nonstrict: whether the time labels $(t_i){i\in[\ell]}$ must be strictly increasing ($t_i<t{i+1}$) or only non-decreasing ($t_i\leq t_{i+1}$)

  The following are possible restriction of the labeling $\lambda$:

  • Simple vs not (Multi-label): whether each edge is allowed at most one label ($\lambda\colon V\rightarrow [\tau]$) or more ($\lambda\colon V\rightarrow 2^\tau$)

  • Proper vs not: whether two incident edges may share a time label or not

    In a proper graph nonstrict and strict behave exactly the same since for any two consecutive time labels $t_i, t_{i+1}$ in a temporal path holds that $t_i\neq t_{i+1}$.

Reachability Problems

Several algorithmic questions arise from temporal reachability:

• Reachability Graph (All-Pairs Reachability): Which vertices can reach one another?
• Earliest Arrival / Latest Departure / Fastest Path: What is the earliest time by which $u$ can reach $v$, or the shortest duration of a $u$-$v$-trip?
• Temporally Connected Components: Find subsets of vertices that can pairwise reach one another.
• Temporal Spanner: Find a minimum subgraph that pertains all reachabilities of the original graph.

These problems are foundational for analyzing temporal graphs and are studied in both theoretical and applied contexts.

Computing the Reachability Graph (All-Pairs Reachability)

The reachability graph $\mathcal{R}(\mathcal{G})$ is a static directed graph $(V,E_c)$ with $(u,v)\in E_c$ if and only if $u$ reaches $v$.

• Streaming algorithm, naive, Single-Source for each vertex $\mathcal{O}(n\cdot M)$
• Streaming algorithm, smarter?
• “Temporal Dijkstra”, on the static expansion, Single-Source for each vertex $\mathcal{O}(..)$

Further Computational Problems

Temporal reachability plays a key role in many domains:

• Realization: Generate a temporal graph which satisfies certain properties, such as constraints on reachabilities.
• Optimize (max/min) reachability: This can be done in the context of Realization or Modification of the temporal graph, which includes adding/removing edges, delaying/advancing edges
• Further problems related to temporal paths: See corresponding page.