A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
ACM Transactions on Computation Theory · 2011
DOI: 10.1145/1944857.1944860 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Michael R. Fellows und 3 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 24 Literaturangaben.
Abstract (Originalsprache)
We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of the following task: given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, find a smaller disjoint solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that a few cases are polynomial-time solvable, and the others are NP-hard. The considered class of vertex deletion problems includes Vertex Cover (where the compression task is polynomial time) and Undirected Feedback Vertex Set (where the compression task is NP-complete).
Zitieren
APA
Fellows, M. R., Guo, J., Moser, H., & Niedermeier, R. (2011). A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. ACM Transactions on Computation Theory. https://doi.org/10.1145/1944857.1944860
Vancouver
Fellows MR, Guo J, Moser H, Niedermeier R. A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. ACM Transactions on Computation Theory. 2011. doi:10.1145/1944857.1944860
BibTeX
@article{Fellows2011,
author = {Fellows, Michael R. and Guo, Jiong and Moser, Hannes and Niedermeier, Rolf},
title = {A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems},
journal = {ACM Transactions on Computation Theory},
year = {2011},
doi = {10.1145/1944857.1944860}
}
EUVIMED