An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz · SIAM Journal on Discrete Mathematics · 2010
The Nemhauser–Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser–Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a $(2-2/d)$-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a $(2-\lg\lg n/2\lg n)$-approximation algorithm for general graphs, and a $2k$ kernel for the parameterized Generalized Vertex Cover problem.