Temporal graph classes: A view through temporal separators

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. 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-complete, 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.

Authors

• Till Fluschnik Department of Computer Science, Humboldt Universität Berlin
• Hendrik Molter Ben Gurion University of the Negev
• Rolf Niedermeier
• Malte Renken Algorithmics and Computational Complexity Group, Technische Universität Berlin
• Philipp Zschoche

Keywords

• Temporal paths
• Temporal restrictions
• Unit interval graphs
• NP-completeness
• Fixed-parameter tractability
• Dynamic programming