A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Michael Fellows; J Guo; H Moser; Rolf Niedermeier

doi:10.1007/978-3-642-03816-7_28

A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Michael Fellows, J Guo, H Moser, Rolf Niedermeier

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

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). � 2011 ACM.

Original language	English
Title of host publication	Lecture Notes in Computer Science, Proceedings MFCS 2009
Place of Publication	Berlin
Publisher	Springer
Pages	319-330
Number of pages	21
Volume	2
DOIs	https://doi.org/10.1007/978-3-642-03816-7_28
Publication status	Published - 2011
Event	International Symposium, Mathematical Foundations of Computer Science (MFCS 2009) - Novy Smokovev, High Tatras, Novy Smokovev, High Tatras, Slovakia Duration: 24 Aug 2009 → 28 Aug 2009 Conference number: 2009

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5734
ISSN (Print)	0302-9743

Conference

Conference	International Symposium, Mathematical Foundations of Computer Science (MFCS 2009)
Abbreviated title	MFCS
Country/Territory	Slovakia
City	Novy Smokovev, High Tatras
Period	24/08/09 → 28/08/09

Access to Document

10.1007/978-3-642-03816-7_28

Cite this

@inproceedings{eebe4ae5da454ce6bf3cd79613fec2b7,

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 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). � 2011 ACM.",

keywords = "Graph algorithms, Hereditary graph properties, Iterative compression, Parameterized complexity, Vertex deletion problems, Algorithms, Graph theory, Polynomial approximation, Computational complexity",

author = "Michael Fellows and J Guo and H Moser and Rolf Niedermeier",

year = "2011",

doi = "10.1007/978-3-642-03816-7_28",

language = "English",

volume = "2",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "319--330",

booktitle = "Lecture Notes in Computer Science, Proceedings MFCS 2009",

address = "Switzerland",

note = "International Symposium, Mathematical Foundations of Computer Science (MFCS 2009), MFCS ; Conference date: 24-08-2009 Through 28-08-2009",

}

Fellows, M, Guo, J, Moser, H & Niedermeier, R 2011, A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. in Lecture Notes in Computer Science, Proceedings MFCS 2009. vol. 2, Lecture Notes in Computer Science , vol. 5734, Springer, Berlin, pp. 319-330, International Symposium, Mathematical Foundations of Computer Science (MFCS 2009), Novy Smokovev, High Tatras, Slovakia, 24/08/09. https://doi.org/10.1007/978-3-642-03816-7_28

A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. / Fellows, Michael; Guo, J; Moser, H et al.

Lecture Notes in Computer Science, Proceedings MFCS 2009. Vol. 2 Berlin : Springer, 2011. p. 319-330 (Lecture Notes in Computer Science ; Vol. 5734).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

AU - Fellows, Michael

AU - Guo, J

AU - Moser, H

AU - Niedermeier, Rolf

N1 - Conference code: 2009

PY - 2011

Y1 - 2011

N2 - 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). � 2011 ACM.

AB - 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). � 2011 ACM.

KW - Graph algorithms

KW - Hereditary graph properties

KW - Iterative compression

KW - Parameterized complexity

KW - Vertex deletion problems

KW - Algorithms

KW - Graph theory

KW - Polynomial approximation

KW - Computational complexity

UR - http://www.mfcs.sk/mfcs2009/

U2 - 10.1007/978-3-642-03816-7_28

DO - 10.1007/978-3-642-03816-7_28

M3 - Conference Paper published in Proceedings

VL - 2

T3 - Lecture Notes in Computer Science

SP - 319

EP - 330

BT - Lecture Notes in Computer Science, Proceedings MFCS 2009

PB - Springer

CY - Berlin

T2 - International Symposium, Mathematical Foundations of Computer Science (MFCS 2009)

Y2 - 24 August 2009 through 28 August 2009

ER -

A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this