2026-07-24T11:54:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24254 2025-11-12T13:39:28Z ddc:004 open_access

Novel Complexity Results for Temporal Separators with Deadlines Dondi, Riccardo Lafond, Manuel Temporal Graphs Graph Algorithms Graph Separators Parameterized Complexity Approximation Complexity We consider two variants, (s,z,𝓁)-Temporal Separator and (s,z,𝓁)-Temporal Cut, respectively, of the vertex separator and the edge cut problem in temporal graphs. The goal is to remove the minimum number of vertices (temporal edges, respectively) in order to delete all the temporal paths that have time travel at most 𝓁 between a source vertex s and target vertex z. First, we solve an open problem in the literature showing that (s,z,𝓁)-Temporal Separator is NP-hard even when the underlying graph has pathwidth bounded by four. We complement this result showing that (s,z,𝓁)-Temporal Separator can be solved in polynomial time for graphs of pathwidth bounded by three. Then we consider the approximability of (s,z,𝓁)-Temporal Separator and we show that it cannot be approximated within factor 2^Ω(log^{1-ε}|V|) for any constant ε > 0, unless NP ⊆ ZPP (V is the vertex set of the input temporal graph) and that the strict version is approximable within factor 𝓁-1 (we show also that it is unliklely that this factor can be improved). Then we consider the (s,z,𝓁)-Temporal Cut problem, we show that it is APX-hard and we present a 2 log₂(2𝓁) approximation algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Riccardo Dondi and Manuel Lafond 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.23 urn:nbn:de:0030-drops-242545 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.23 eng https://creativecommons.org/licenses/by/4.0/legalcode