Back to Search
Start Over
Temporal Graph Classes: A View Through Temporal Separators
- Publication Year :
- 2018
-
Abstract
- 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.<br />Comment: arXiv admin note: text overlap with arXiv:1711.00963
- Subjects :
- Computer Science - Computational Complexity
F.2.2
G.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1803.00882
- Document Type :
- Working Paper