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

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 Dive into the research topics of 'A complexity dichotomy for finding disjoint Solutions of vertex deletion problems'. Together they form a unique fingerprint.

## Cite this

Fellows, M., Guo, J., Moser, H., & Niedermeier, R. (2011). A complexity dichotomy for finding disjoint Solutions of vertex deletion problems.

*ACM Transactions on Computation Theory*,*2*(5), 5-25. https://doi.org/10.1145/1944857.1944860