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 (2009). A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In: International Symposium, Mathematical Foundations of Computer Science. MFCS 2009., Novy Smokovev, High Tatras, .

Document type: Conference Paper

IRMA ID 81144320xPUB1
Author Fellows, Michael R.
Guo, Jiong
Moser, Hannes
Niedermeier, Rolf
Title A complexity dichotomy for finding disjoint solutions of vertex deletion problems
Conference Name International Symposium, Mathematical Foundations of Computer Science. MFCS 2009.
Conference Location Novy Smokovev, High Tatras
Conference Publication Title Lecture Notes in Computer Science, Proceedings MFCS 2009
Place of Publication Berlin
Publisher Springer-Verlag
Publication Year 2009
Volume Number 5734
Issue Number 2009
Start Page 319
End Page 330
Total Pages 11
Field of Research 0199 - Other Mathematical Sciences
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).
DOI http://dx.doi.org/10.1007/978-3-642-03816-7_28   (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: 210 Abstract Views  -  Detailed Statistics
Created: Tue, 28 Feb 2012, 23:08:55 CST