The study of temporal separators investigates the deletion of vertices, vertex-time pairs, or edges in order to block all temporal paths between two nodes in a time-evolving graph. This is a natural generalization of classic ($s$,$z$)-separation in static graphs to the temporal setting, but it introduces new algorithmic challenges due to the directionality and non-transitivity of temporal paths.
This problem is the dual of computing maximal temporal flows from $s$ to $z$ and closely related to concepts like Menger’s Theorem.
There exist several variants of temporal separators, depending on whether the goal is to remove vertices, edges, or departure times (vertex-time pairs), and what setting the temporal graph is in ((non-)strict, simple, proper, (un)directed).. These differences affect the computational complexity of the corresponding separation problem. The default is cutting vertices.
<aside> 💡
Definition. (temporal $(s,z)$-separator)
Let $\mathcal{G}=(V,E,\lambda)$ be a temporal graph with lifetime $\tau$, and $s,z\in V$.
A vertex set $S$ with $S\cap\{s,z\}=\emptyset$ is a temporal $(s,z)$-separator if there is no temporal $s$-$z$-path in $\mathcal{G}-S$.
</aside>
We denote the number of vertices by $n$, the number of static edges by $m$, and the number of temporal edges by $M=\lvert \mathcal{E}\rvert$.
Complexity (Computational, Parameterized)
The strict version can be reduced to the non-strict version:
<aside> 💡
Lemma 2.1. There is a linear-time many-one reduction from Strict Temporal (s, z)-Separation to Non-Strict Temporal (s, z)-Separation that maps any instance $(\mathcal{G} = (V, E, \tau), s, z, k)$ to an instance $(\mathcal{G}' = (V', E', \tau'), s, z, k')$ with $k' = k$ and $\tau' = 2 \cdot \tau$.
(Semaphore construction) transformation: semaphore
</aside>
<aside> 💡
Definition. (temporal core)
For a temporal graph $\mathcal{G} = (V, \mathcal{E}, \tau)$, the vertex set $W = \left\{ v \in V \,\middle|\, \exists \{v, w\} \in \left( \bigcup_{i=1}^{\tau} E_i \right) \setminus \left( \bigcap_{i=1}^{\tau} E_i \right) \right\} \subseteq V$ is called the temporal core.
It is the number of vertices for which at least one adjacent edge changes over time (is sometime present but not always).
</aside>