  We study temporal analogues of the Unrestricted Vertex Separator problem from
the static world. An $(s,z)$-temporal separator is a set of vertices whose
removal disconnects vertex $s$ from vertex $z$ for every time step in a
temporal graph. The $(s,z)$-Temporal Separator problem asks to find the minimum
size of an $(s,z)$-temporal separator for the given temporal graph. We
introduce a generalization of this problem called the $(s,z,t)$-Temporal
Separator problem, where the goal is to find a smallest subset of vertices
whose removal eliminates all temporal paths from $s$ to $z$ which take less
than $t$ time steps. Let $\tau$ denote the number of time steps over which the
temporal graph is defined (we consider discrete time steps). We characterize
the set of parameters $\tau$ and $t$ when the problem is $\mathcal{NP}$-hard
and when it is polynomial time solvable. Then we present a $\tau$-approximation
algorithm for the $(s,z)$-Temporal Separator problem and convert it to a
$\tau^2$-approximation algorithm for the $(s,z,t)$-Temporal Separator problem.
We also present an inapproximability lower bound of $\Omega(\ln(n) +
\ln(\tau))$ for the $(s,z,t)$-Temporal Separator problem assuming that
$\mathcal{NP}\not\subset\mbox{\sc Dtime}(n^{\log\log n})$. Then we consider
three special families of graphs: (1) graphs of branchwidth at most $2$, (2)
graphs $G$ such that the removal of $s$ and $z$ leaves a tree, and (3) graphs
of bounded pathwidth. We present polynomial-time algorithms to find a minimum
$(s,z,t)$-temporal separator for (1) and (2). As for (3), we show a
polynomial-time reduction from the Discrete Segment Covering problem with
bounded-length segments to the $(s,z,t)$-Temporal Separator problem where the
temporal graph has bounded pathwidth.

Data Structures and Algorithms