A Generalization of Nemhauser and Trotter's Local Optimization Theorem

Michael R. Fellows, Jiong Guo, Hannes Moser & Rolf Niedermeier
The Nemhauser-Trotter local optimization theorem applies to the NP-hard \textsc{Vertex Cover} problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter's result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). We exhibit our framework using a generalization of \textsc{Vertex Cover}, called \textrm{\sc Bounded-Degree Deletion}, that has...