The dilation is a transformation that converts any undirected non-strict temporal graph into a support-equivalent graph in the proper setting. Since proper graphs make the strict/non-strict distinction irrelevant (adjacent edges never share a label, so all paths are automatically strict), dilation effectively eliminates the non-strict aspect while preserving full path structure.
| Input | Any UD & non-strict temporal graph $\mathcal{G} = (V, E, \lambda)$ with lifetime $\Lambda$ |
| Output | A UD & proper temporal graph $\mathcal{H}$ |
| Equivalence | Support equivalence: same vertex set, same set of path-supports |
| Vertex blowup | None (same vertex set) |
| Lifetime blowup | Increases lifetime (label shifting to resolve conflicts) |
The dilation processes each snapshot $G_t$ and replaces simultaneous edge appearances with a sequence of shifted labels. Within a single snapshot, edges incident to the same vertex that share a time label are spread apart in time. This is done carefully so that any non-strict temporal path in $\mathcal{G}$ corresponds to a (now strict) temporal path in $\mathcal{H}$ visiting the same vertices in the same order, and vice versa.
The key insight is that non-strict paths through a snapshot (using multiple edges at the same time) can be simulated by a rapid sequence of edges at nearby times.
Dilation is one of the three core transformations from CCS24. Together with saturation and the semaphore construction, it enables the chain:
$\text{any UD setting} \xrightarrow{\text{dilation}} \text{UD \& proper} \xrightarrow{\text{identity}} \text{UD \& strict}$
Since support equivalence implies reachability equivalence, dilation also shows: UD & non-strict $\rightsquigarrow_R$ UD & proper.