AN EXTENSION OF THE NEMHAUSER-TROTTER THEOREM TO GENERALIZED VERTEX COVERWITH APPLICATIONS

作者：Bar Yehuda Reuven^*; Hermelin Danny; Rawitz Dror

来源：SIAM Journal on Discrete Mathematics, 2010, 24(1): 287-300.

DOI：10.1137/090773313

• approximation algorithms
• generalized vertex cover
• local ratio technique
• Nemhauser-Trotter theorem

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.

• 出版日期2010