A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

摘要

We study the PARTIAL VERTEX COVER problem, a generalization of the well-known VERTEX COVER problem. Given a graph G = (V, E) and an integer s, the goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(V log V + E) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be applied to a more general version of the problem. In the PARTIAL CAPACITATED VERTEX COVER problem each vertex u comes with a capacity k_u and a weight w_u. A solution consists of a function x : V → No and an orientation of all but s edges, such that the number edges oriented toward any vertex u is at most x_uk_u. The cost of the cover is given by ∑_(v∈V)x_vw_v. Our objective is to find a cover with minimum cost. We provide an algorithm with the same performance guarantee as for regular partial vertex cover. In this case no algorithm for the problem was known.