Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications

摘要

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 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.