Dynamic Problems on Static Graphs: The Time Dimension

Static network models capture where commodities can flow, but real networks have a second dimension: when. A truck takes hours to travel from city $A$ to city $B$. A packet takes milliseconds to cross a router. To model dynamic flow on a static graph, we use the time-expanded graph.

Given a static graph $G=(V,E)$ and a discrete time horizon $T,$ the time-expanded graph $G^T=(V^T,E^T)$ replicates each node of $G$ once per time step. Formally,

$$V^T = \{\, v_t \,:\, v\in V,\ t\in\{0,1,2,\ldots,T\}\,\}.$$

The node $v_t$ represents "being at $v$ at time $t$." Because the time index ranges over $T+1$ values $\{0,1,\ldots,T\},$ the time-expanded node set has size

$$|V^T| = (T+1)\cdot|V|.$$

For instance, a static graph with $|V|=3$ nodes and horizon $T=4$ produces a time-expanded graph with $(4+1)\cdot 3 = 15$ nodes.