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.
The directed semaphore (Definition 4.22, full version) adapts the technique to directed temporal graphs. The key difference is that directed edges carry an inherent orientation, so: