A generalization of Nemhauser and Trotter's local optimization theorem

作者：Fellows Michael R; Guo Jiong^*; Moser Hannes; Niedermeier Rolf

来源：Journal of Computer and System Sciences, 2011, 77(6): 1141-1158.

DOI：10.1016/j.jcss.2010.12.001

• Parameterized computational complexity
• NP-hard problems
• W[2]-completeness
• Graph algorithms
• Polynomial-time data reduction
• Kernelization

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 epsilon > 0, an O(k(1+epsilon))-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.

• 出版日期2011-11