### Abstract

Original language | English |
---|---|

Pages (from-to) | 5-25 |

Number of pages | 21 |

Journal | ACM Transactions on Computation Theory |

Volume | 2 |

Issue number | 5 |

DOIs | |

Publication status | Published - 2011 |

### Fingerprint

### Cite this

*ACM Transactions on Computation Theory*,

*2*(5), 5-25. https://doi.org/10.1145/1944857.1944860

}

*ACM Transactions on Computation Theory*, vol. 2, no. 5, pp. 5-25. https://doi.org/10.1145/1944857.1944860

**A complexity dichotomy for finding disjoint Solutions of vertex deletion problems.** / Fellows, Michael; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

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

AU - Fellows, Michael

AU - Guo, Jiong

AU - Moser, Hannes

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

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

U2 - 10.1145/1944857.1944860

DO - 10.1145/1944857.1944860

M3 - Article

VL - 2

SP - 5

EP - 25

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

SN - 1942-3454

IS - 5

ER -