2021/07/04 by Molter, Hendrik
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2107.01609
In this work, we investigate the computational complexity of Restless Temporal (s,z)-Separation, where we are asked whether it is possible to destroy all restless temporal paths between two distinct vertices s and z by deleting at most k vertices from a temporal graph. A temporal graph has a fixed vertex but the edges have (discrete) time stamps. A restless temporal path uses edges with non-decreasing time stamps and the time spent at each vertex must not exceed a given duration Δ. Restless Temporal (s,z)-Separation naturally generalizes the NP-hard Temporal (s,z)-Separation problem. We show that Restless Temporal (s,z)-Separation is complete for Σ2P, a complexity class located in the second level of the polynomial time hierarchy. We further provide some insights in the parameterized complexity of Restless Temporal (s,z)-Separation parameterized by the separator size k.