2026-07-22T13:50:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19340 2024-03-06T11:03:49Z ddc:004 open_access

Temporal Separators with Deadlines Harutyunyan, Hovhannes A. Koupayi, Kamran Pankratov, Denis Temporal graphs dynamic graphs vertex separator vertex cut separating set deadlines inapproximability approximation algorithms 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. The (s,z)-Temporal Separator problem is known to be NP-hard in general, although some special cases (such as bounded treewidth) admit efficient algorithms [Fluschnik et al., 2020]. 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 τ denote the number of time steps over which the temporal graph is defined (we consider discrete time steps). We characterize the set of parameters τ and t when the problem is NP-hard and when it is polynomial time solvable. Then we present a τ-approximation algorithm for the (s,z)-Temporal Separator problem and convert it to a τ²-approximation algorithm for the (s,z,t)-Temporal Separator problem. We also present an inapproximability lower bound of Ω(ln(n) + ln(τ)) for the (s,z,t)-Temporal Separator problem assuming that NP ⊄ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hovhannes A. Harutyunyan and Kamran Koupayi and Denis Pankratov 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.38 urn:nbn:de:0030-drops-193407 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.38 eng https://creativecommons.org/licenses/by/4.0/legalcode