A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Michael Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

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

    Fingerprint

    Dichotomy
    Deletion
    Computational complexity
    Disjoint
    Compression
    Polynomials
    Vertex of a graph
    NP-complete problem
    Feedback
    Polynomial time
    Computational Complexity
    Feedback Vertex Set
    Minimal Solution
    Vertex Cover
    NP-hard Problems
    Undirected Graph
    Minimization Problem
    Inclusion
    Graph in graph theory
    Class

    Cite this

    Fellows, Michael ; Guo, Jiong ; Moser, Hannes ; Niedermeier, Rolf. / A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. In: ACM Transactions on Computation Theory. 2011 ; Vol. 2, No. 5. pp. 5-25.
    @article{3f41480246d34de8a5c01c8628ac4ec3,
    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).",
    author = "Michael Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier",
    year = "2011",
    doi = "10.1145/1944857.1944860",
    language = "English",
    volume = "2",
    pages = "5--25",
    journal = "ACM Transactions on Computation Theory",
    issn = "1942-3454",
    publisher = "Association for Computing Machinery (ACM)",
    number = "5",

    }

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

    In: ACM Transactions on Computation Theory, Vol. 2, No. 5, 2011, p. 5-25.

    Research output: Contribution to journalArticleResearchpeer-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 -