  Temporal graphs are graphs with time-stamped edges. We study the problem of
finding a small vertex set (the separator) with respect to two designated
terminal vertices such that the removal of the set eliminates all temporal
paths connecting one terminal to the other. Herein, we consider two models of
temporal paths: paths that pass through arbitrarily many edges per time step
(non-strict) and paths that pass through at most one edge per time step
(strict). Regarding the number of time steps of a temporal graph, we show a
complexity dichotomy (NP-hardness versus polynomial-time solvability) for both
problem variants. Moreover we prove both problem variants to be NP-complete
even on temporal graphs whose underlying graph is planar. We further show that,
on temporal graphs with planar underlying graph, if additionally the number of
time steps is constant, then the problem variant for strict paths is solvable
in quasi-linear time. Finally, we introduce and motivate the notion of a
temporal core (vertices whose incident edges change over time). We prove that
the non-strict variant is fixed-parameter tractable when parameterized by the
size of the temporal core, while the strict variant remains NP-complete, even
for constant-size temporal cores.
