2010 | OriginalPaper | Chapter
Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
Authors : Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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-\frac{2}{d})$
-approximation algorithm for graphs of bounded degree
d
, a PTAS for planar graphs, a
$(2-\frac{\lg \lg n}{2 \lg n})$
-approximation algorithm for general graphs, and a 2
k
kernel for the parameterized
Generalized Vertex Cover
problem.