The complexity of finding small separators in temporal graphs

摘要

Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those 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-completeness 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. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores.