2026-09-08T02:22:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26248 2026-09-05T19:39:22Z ddc:004 open_access

Robust Temporal Cut Enright, Jessica Erlebach, Thomas Meeks, Kitty Morawietz, Nils temporal graphs minimum cut parameterized complexity FPT algorithms In this paper we introduce the Robust Temporal Cut problem (RTC) defined as follows: For a given temporal graph with designated source node s and destination node z, and parameters δ and k, remove a minimum number of time edges so that, even if an adversary can adjust the time labels of up to k of the remaining time edges by adding or subtracting values bounded by δ, no temporal s-z path exists. We study the classical and parameterized complexity of RTC. In particular, we show for both strict and non-strict temporal paths that RTC is NP-complete for any combination of k ≥ 1 and δ ≥ 1 and W[1]-hard for parameter solution size or vertex interval membership width plus pathwidth of the underlying graph. Furthermore, we give approximation algorithms and FPT algorithms for parameters including temporal neighborhood diversity plus solution size, timed vertex cover size, and vertex cover size of the underlying graph plus solution size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jessica Enright and Thomas Erlebach and Kitty Meeks and Nils Morawietz 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.14 urn:nbn:de:0030-drops-262480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode