<aside>

============== Under Construction ==============

</aside>

The static expansion (also called time-expanded or time-unrolled) is the standard tool for reducing questions about a temporal graph $\mathcal{G}=(V,E,\lambda)$ to questions about an ordinary directed static graph. Time is made explicit in the vertex set: vertices are copied per time step, waiting arcs link consecutive copies of the same vertex to model the passage of time, and every temporal edge becomes an arc between the appropriate time copies of its endpoints.

Temporal walks in $\mathcal{G}$ then correspond exactly to directed walks in the expansion, so much of the classical static toolbox — reachability, shortest/fastest paths, flows, cuts, and Menger-type theorems — carries over to the temporal setting. The downside of these static expansions is that vertex identity is lost, since each vertex is spread out into its different time appearances. This makes it for example impossible to compute static-vertex-disjoint or static-edge-disjoint temporal paths using the static expansion.

Two complementary realizations recur in the literature: a vertex expansion whose nodes are $(\text{vertex},\text{time})$ pairs, and an edge expansion whose nodes are the temporal edges themselves; they differ mainly in size and in which problems they make convenient.

The sections below give the precise definitions, sizes, and construction times of both variants, and the toggles collect the literature that introduced or used such expansions.

History on expansions

Literature on expansions

1. Vertex Expansion

<aside> 💡

Definition. [static expansion / time-expanded graph]

The static expansion of $\mathcal{G}$ is a directed static graph $\mathrm{Exp}(\mathcal{G}) = (V', E')$ constructed as follows.

• Time-layered vertices

  For every vertex $v\in V$ and every time label $t\in [\Lambda]$, create a copy $v^t \in V'$.

• Forward (stay) edges — waiting

  For every vertex $v\in V$ and each pair of consecutive times $t, t'\in\Lambda$ with $t \le t'$, add:

  • Non-strict expansion:

    Add a directed edge $(v^t \to v^{t'})$ whenever $t' \ge t$.

  • Strict expansion:

    Add a directed edge $(v^t \to v^{t'})$ whenever $t' > t$.

  These edges model the ability to wait at a vertex until a later time.

• Traversal edges — using temporal edges

  For every temporal edge $(u,v)\in E_t$ (undirected case) or $u\to v\in E_t$ (directed case), add:

  • a directed edge $(u^t \to v^{t})$
  • and if undirected, also $(v^t \to u^{t})$.

  These edges model traversing a temporal edge exactly at time $t$.

  (If travel times are present, replace arrival time by $t+\tau(e,t)$.)

</aside>

The definition is given in the callout above. Throughout, let $n=|V|$, let $\Lambda$ be the number of distinct time labels (the lifetime), and let $M=\sum_{t\in\Lambda}|E_t|$ be the total number of temporal edges (time-edge appearances).

Size

• Vertices. One copy per vertex per label: $|V'| = n\,\Lambda$.
• Edges. Waiting arcs along consecutive layers contribute $n(\lambda-1)$, and each temporal edge contributes one traversal arc (two if undirected): $|E'| = n(\Lambda-1) + M$ in the directed case and $n(\Lambda-1) + 2M$ in the undirected case.
• Overall the expansion has size $\Theta(n\Lambda + M)$.

Computation

Sort the labels once ($O(\Lambda\log\Lambda)$, or $O(\Lambda)$ by bucketing integer labels); allocate the $n\Lambda$ time copies together with their $n(\Lambda-1)$ waiting arcs; then scan the temporal edges once, adding one arc per appearance. This builds $\mathrm{Exp}(\mathcal{G})$ in $O(n\Lambda + M)$ time and space — linear in the output. Temporal $s$–$t$ reachability or earliest-arrival then reduces to a single BFS/DFS in $O(n\Lambda + M)$.

2. Edge Expansion

Definition

The edge expansion (temporal line graph) makes the temporal edges the vertices. For $\mathcal{G}=(V,E,\lambda)$ build a directed static graph $\mathrm{Exp}_E(\mathcal{G})$:

• Edge nodes. For every temporal edge $a=(u,v)\in E_t$ create a node $\langle a\rangle$ (for undirected $\mathcal{G}$, one node per orientation).