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 Proceedings

    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

    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). Springer. https://doi.org/10.1007/978-3-642-03816-7_28