2018/03/01 by Fluschnik, Till, Molter, Hendrik, Niedermeier, Rolf +2 · 2 citations
#Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1803.00882
We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s, z)-Separation problem is NP-hard, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph---there we observe polynomial-time solvability in the case of bounded treewidth---as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.