Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

A generalization of Nemhauser and Trotter's local optimization theorem

Fellows, Michael, Guo, Jiong, Moser, Hannes and Niedermeier, Rolf (2011). A generalization of Nemhauser and Trotter's local optimization theorem. Journal of Computer and System Sciences,77(6):1141-1158.

Document type: Journal Article

ISI LOC 000294833400014
Title A generalization of Nemhauser and Trotter's local optimization theorem
Author Fellows, Michael
Guo, Jiong
Moser, Hannes
Niedermeier, Rolf
Journal Name Journal of Computer and System Sciences
Publication Date 2011
Volume Number 77
Issue Number 6
ISSN 0022-0000   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-80052336275
Start Page 1141
End Page 1158
Total Pages 18
Place of Publication United States
Publisher Academic Press
HERDC Category C1 - Journal Article (DIISR)
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
NP-hard problems
Parameterized computational complexity
Polynomial-time data reduction
DOI   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
Version Filter Type
Access Statistics: 56 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:59:09 CST