Paper Info
Title
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Abstract
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, given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, to find a better 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, except for few cases which are polynomial-time solvable, the others are NP-complete. This class includes problems such as Vertex Cover (here the corresponding compression task is decidable in polynomial time) or Undirected Feedback Vertex Set (here the corresponding compression task is NP-complete).
Year
DOI
Venue
2011
10.1145/1944857.1944860
TOCT
Keywords
Field
DocType
iterative compression,hereditary graph properties,parameterized complexity,vertex deletion problems,inclusion-minimal solution,graph algorithms,following task,considered class,undirected feedback vertex set,vertex cover,np-hard minimization problem,compression task,vertex deletion problem,complexity dichotomy,finding disjoint solutions,computational complexity,feedback vertex set,polynomial time,algorithms
Discrete mathematics,Combinatorics,Parameterized complexity,Vertex (geometry),Vertex (graph theory),Vertex cover,Iterative compression,Time complexity,Feedback vertex set,Mathematics,Computational complexity theory
Journal
Volume
Issue
ISSN
2
2
0302-9743
Citations 
PageRank 
References 
8
0.58
22
Authors
4
Name
Order
Citations
PageRank
Michael R. Fellows14138319.37
Jiong Guo2149388.91
Hannes Moser336219.54
Rolf Niedermeier43465234.21