A generalization of Nemhauser and Trotters local optimization theorem

Michael Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number6
    Publication statusPublished - Nov 2011


    Dive into the research topics of 'A generalization of Nemhauser and Trotters local optimization theorem'. Together they form a unique fingerprint.

    Cite this