A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Michael Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

    Research output: Contribution to journalArticle

    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 languageEnglish
    Pages (from-to)5-25
    Number of pages21
    JournalACM Transactions on Computation Theory
    Volume2
    Issue number5
    DOIs
    Publication statusPublished - 2011

      Fingerprint

    Cite this