Approximation algorithms for the partition vertex cover problem

作者：Bera Suman K^*; Gupta Shalmoli; Kumar Amit; Roy Sambuddha

来源：Theoretical Computer Science, 2014, 555: 2-8.

DOI：10.1016/j.tcs.2014.04.006

• Approximation algorithm
• Vertex cover
• Knapsack cover inequality
• LP rounding

We consider a natural generalization of the Partial vertex cover problem. Here an instance consists of a graph G = (V, E), a cost function c: V -%26gt; Z(+), a partition P-1, ..., P-r of the edge set E, and a parameter k(i) for each partition P-i. The objective is to find a minimum cost set of vertices which cover at least k(i) edges from the partition P-i. We call this the Partition-VC problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of O (logr), where r is the number of sets in the partition of the edge set. We also extend our result to more general settings. For example we consider a problem where additionally edges have profits, and we would like to pick a minimum cost set of vertices which cover edges of total profit at least Pi(i) for each partition P-i. We call this the Knapsack Partition Vertex Cover problem. We give an O (logr) approximation algorithm for this problem as well.

• 出版日期2014-10-23
• 单位IBM