Zschoche, Philipp ;
Fluschnik, Till ;
Molter, Hendrik ;
Niedermeier, Rolf
The Complexity of Finding Small Separators in Temporal Graphs
Abstract
Temporal graphs are graphs with timestamped 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 (nonstrict) 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 (NPhardness versus polynomialtime solvability) for both problem variants. Moreover we prove both problem variants to be NPcomplete 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 quasilinear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the nonstrict variant is fixedparameter tractable when parameterized by the size of the temporal core, while the strict variant remains NPcomplete, even for constantsize temporal cores.
BibTeX  Entry
@InProceedings{zschoche_et_al:LIPIcs:2018:9627,
author = {Philipp Zschoche and Till Fluschnik and Hendrik Molter and Rolf Niedermeier},
title = {{The Complexity of Finding Small Separators in Temporal Graphs}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {45:145:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9627},
URN = {urn:nbn:de:0030drops96277},
doi = {10.4230/LIPIcs.MFCS.2018.45},
annote = {Keywords: (non)strict temporal paths, temporal core, singlesource shortest paths, node multiway cut, lengthbounded cuts, parameterized complexity}
}
2018
Keywords: 

(non)strict temporal paths, temporal core, singlesource shortest paths, node multiway cut, lengthbounded cuts, parameterized complexity 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

2018 