### Abstract

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 | |

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 | Slovakia |

City | Novy Smokovev, High Tatras |

Period | 24/08/09 → 28/08/09 |

### Fingerprint

### Cite this

*Lecture Notes in Computer Science, Proceedings MFCS 2009*(Vol. 2, pp. 319-330). (Lecture Notes in Computer Science ; Vol. 5734). Berlin: Springer. https://doi.org/10.1007/978-3-642-03816-7_28

}

*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; Niedermeier, Rolf.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › Research › 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

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

ER -