A generalization of Nemhauser and Trotterʼs local optimization theorem

• Published in: Journal of computer and system sciences 2011-11, Vol.77 (6), p.1141-1158
• Main Authors: Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf
• Format: Article
• Language: English
• Subjects: Graph algorithms; Kernelization; NP-hard problems; Parameterized computational complexity; Polynomial-time data reduction; W-completeness
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2010.12.001

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 Trotterʼs 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 ( k 1 + ϵ ) -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.