<aside> 🌐
Outdated page — the Temporal Graph Wiki has moved. Read this page on temporalgraph.wiki.
</aside>
The semaphore construction is a transformation technique on temporal graphs. It converts any strict temporal graph into an induced-reachability equivalent graph in the proper & simple (also called happy) setting. Since proper & simple is the most restricted setting, this transformation — combined with dilation — implies that all temporal graph settings are induced-reachability equivalent.
| Input | Any (D or UD) & strict temporal graph $\mathcal{G} = (V, E, \lambda)$ |
| Output | A (D or UD) & proper & simple temporal graph $\mathcal{H}$ |
| Equivalence | Induced-reachability equivalence: $V \subseteq V(\mathcal{H})$ and $R(\mathcal{G}) \cong R(\mathcal{H})[V]$ |
| Vertex blowup | Introduces one auxiliary vertex $x_t$ per temporal edge $(e, t) \in \mathcal{E}$ |
| Lifetime blowup | Significant (snapshot-by-snapshot label shifting) |
The semaphore construction proceeds in two phases.
Each temporal edge $(uv, t)$ is replaced by a path of length 2 through a fresh auxiliary vertex $x_t$:
$uv \xrightarrow{t} \quad \Longrightarrow \quad u \xrightarrow{t} x_t \xrightarrow{t} v$
The auxiliary vertex $x_t$ is unique to the temporal edge $(uv, t)$, ensuring each edge in $\mathcal{H}$ receives exactly one time label (simple).
To ensure no two edges incident to the same vertex share a time label, the construction processes each snapshot $\mathcal{G}_t$ individually. Within a snapshot, every subdivided edge (now a 2-path through $x_t$) is duplicated, and the labels of the two copies are shifted apart:
This ensures that adjacent temporal edges in $\mathcal{H}$ never share a time label, making the result proper.