A complexity dichotomy for finding disjoint Solutions of vertex deletion problems

Michael Fellows, J Guo, H Moser, Rolf Niedermeier

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-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). � 2011 ACM.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science, Proceedings MFCS 2009
    Place of PublicationBerlin
    PublisherSpringer
    Pages319-330
    Number of pages21
    Volume2
    DOIs
    Publication statusPublished - 2011
    EventInternational Symposium, Mathematical Foundations of Computer Science (MFCS 2009) - Novy Smokovev, High Tatras, Novy Smokovev, High Tatras, Slovakia
    Duration: 24 Aug 200928 Aug 2009
    Conference number: 2009

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume5734
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Symposium, Mathematical Foundations of Computer Science (MFCS 2009)
    Abbreviated titleMFCS
    CountrySlovakia
    CityNovy Smokovev, High Tatras
    Period24/08/0928/08/09

    Fingerprint

    Computational complexity
    Polynomials
    Feedback

    Cite this

    Fellows, M., Guo, J., Moser, H., & Niedermeier, R. (2011). A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. In 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
    Fellows, Michael ; Guo, J ; Moser, H ; Niedermeier, Rolf. / A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. Lecture Notes in Computer Science, Proceedings MFCS 2009. Vol. 2 Berlin : Springer, 2011. pp. 319-330 (Lecture Notes in Computer Science ).
    @inproceedings{eebe4ae5da454ce6bf3cd79613fec2b7,
    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). � 2011 ACM.",
    keywords = "Graph algorithms, Hereditary graph properties, Iterative compression, Parameterized complexity, Vertex deletion problems, Algorithms, Graph theory, Polynomial approximation, Computational complexity",
    author = "Michael Fellows and J Guo and H Moser and Rolf Niedermeier",
    year = "2011",
    doi = "10.1007/978-3-642-03816-7_28",
    language = "English",
    volume = "2",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "319--330",
    booktitle = "Lecture Notes in Computer Science, Proceedings MFCS 2009",
    address = "Switzerland",

    }

    Fellows, M, Guo, J, Moser, H & Niedermeier, R 2011, A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. in 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.

    Lecture Notes in Computer Science, Proceedings MFCS 2009. Vol. 2 Berlin : Springer, 2011. p. 319-330 (Lecture Notes in Computer Science ; Vol. 5734).

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-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 -

    Fellows M, Guo J, Moser H, Niedermeier R. A complexity dichotomy for finding disjoint Solutions of vertex deletion problems. In Lecture Notes in Computer Science, Proceedings MFCS 2009. Vol. 2. Berlin: Springer. 2011. p. 319-330. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-642-03816-7_28