“Space and time emerged together and are inseparable; the universe has no center, because every point is expanding away from every other.”
Stephen Hawking
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>
The semantics of reachability change depending on the Temporal Graph Settings. There are 4 dimensions to a temporal graph:
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
Note that in a proper graph the notion of nonstrict and strict behave exactly the same as there can be no temporal path with two time labels being the same $t_i\neq t_{i+1}$.
Temporal reachability can behave very differently depending on the temporal setting. For more details, see: [Reachabilities Impacted by Temporal Graph Settings — [CCS24] and [D25]](https://temporalgraph.notion.site/Reachabilities-Impacted-by-Temporal-Graph-Settings-CCS24-and-D25-11843d6e8b7c8041a9cde87728cfea59)
Several algorithmic questions arise from temporal reachability:
These problems are foundational for analyzing time-varying networks and are studied in both theoretical and applied contexts.
<aside> 💡
Definition.
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$.
</aside>