Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

A complexity dichotomy for finding disjoint solutions of vertex deletion problems

Fellows, Michael R., Guo, Jiong, Moser, Hannes and Niedermeier, Rolf (2011). A complexity dichotomy for finding disjoint solutions of vertex deletion problems. ACM Transactions on Computation Theory,2(5):5-25.

Document type: Journal Article

IRMA ID CDU0002xPUB22
Title A complexity dichotomy for finding disjoint solutions of vertex deletion problems
Author Fellows, Michael R.
Guo, Jiong
Moser, Hannes
Niedermeier, Rolf
Journal Name ACM Transactions on Computation Theory
Publication Date 2011
Volume Number 2
Issue Number 5
ISSN 1942-3454   (check CDU catalogue open catalogue search in new window)
Start Page 5
End Page 25
Total Pages 21
Place of Publication United States
Publisher A C M Special Interest Group
HERDC Category C1 - Journal Article (DIISR)
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 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).
DOI http://dx.doi.org/10.1145/1944857.1944860   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 95 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:59:16 CST