A generalization of Nemhauser and Trotters local optimization theorem

Michael Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.
    Original languageEnglish
    Pages (from-to)1141-1158
    Number of pages18
    JournalJournal of Computer and System Sciences
    Volume77
    Issue number6
    DOIs
    Publication statusPublished - Nov 2011

    Fingerprint

    Optimization Theorems
    Local Optimization
    Vertex Degree
    Linear programming
    Deletion
    Vertex Cover
    Vertex of a graph
    kernel
    Combinatorial argument
    Iterative Process
    Graph in graph theory
    Solution Set
    Cardinality
    Completeness
    NP-complete problem
    Linearly
    Generalization
    Transform
    Imply
    Generalise

    Cite this

    Fellows, Michael ; Guo, Jiong ; Moser, Hannes ; Niedermeier, Rolf. / A generalization of Nemhauser and Trotters local optimization theorem. In: Journal of Computer and System Sciences. 2011 ; Vol. 77, No. 6. pp. 1141-1158.
    @article{cbab3e3bbc1d493ab2faddce733abd5e,
    title = "A generalization of Nemhauser and Trotters local optimization theorem",
    abstract = "The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away {"}easy parts{"} of the input instance, finally leaving a {"}hard core{"} whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.",
    keywords = "Graph algorithms, Kernelization, NP-HARD problem, Parameterized, Polynomial-time, Approximation algorithms, Data reduction, Linear programming, Optimization, Parameterization, Computational complexity",
    author = "Michael Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier",
    year = "2011",
    month = "11",
    doi = "10.1016/j.jcss.2010.12.001",
    language = "English",
    volume = "77",
    pages = "1141--1158",
    journal = "Journal of Computer and System Sciences",
    issn = "0022-0000",
    publisher = "Academic Press",
    number = "6",

    }

    A generalization of Nemhauser and Trotters local optimization theorem. / Fellows, Michael; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf.

    In: Journal of Computer and System Sciences, Vol. 77, No. 6, 11.2011, p. 1141-1158.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - A generalization of Nemhauser and Trotters local optimization theorem

    AU - Fellows, Michael

    AU - Guo, Jiong

    AU - Moser, Hannes

    AU - Niedermeier, Rolf

    PY - 2011/11

    Y1 - 2011/11

    N2 - The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.

    AB - The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.

    KW - Graph algorithms

    KW - Kernelization

    KW - NP-HARD problem

    KW - Parameterized

    KW - Polynomial-time

    KW - Approximation algorithms

    KW - Data reduction

    KW - Linear programming

    KW - Optimization

    KW - Parameterization

    KW - Computational complexity

    UR - http://www.scopus.com/inward/record.url?scp=80052336275&partnerID=8YFLogxK

    U2 - 10.1016/j.jcss.2010.12.001

    DO - 10.1016/j.jcss.2010.12.001

    M3 - Article

    VL - 77

    SP - 1141

    EP - 1158

    JO - Journal of Computer and System Sciences

    JF - Journal of Computer and System Sciences

    SN - 0022-0000

    IS - 6

    ER -