文摘
The Nemhauser¨CTrotter 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¨CTrotter 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 , 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 . Our generalization of the Nemhauser¨CTrotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an -vertex problem kernel for and, for any , an -vertex problem kernel for . Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.
