Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.

It is easy to see that this problem is inapproximable unless studied in a bi-criteria setting. We know a very simple LP-rounding algorithm for this problem that is a $(3,3)$ bi-criteria approximation.

Q. Has this problem been studied in the literature elsewhere, perhaps with a different name? Are there any known combinatorial approximation algorithms for this problem?

Clarification: The objective of this problem is to output a set of vertices $S$ that minimize the number of uncovered edges in $G = (V,E)$. The number of uncovered edges is equal to the number of edges in $E$ that have neither end point in $S$.

  • $\begingroup$ @NealYoung Yes, perhaps it would be better to migrate this question to cstheory.se. Just to clarify, for $\alpha, \beta \ge 1$, an $(\alpha,\beta)$ bi-criteria approximation means that the solution I output has has size at most $\beta k$ and the number of uncovered edges corresponding to this solution is within an $\alpha$ factor of the number of uncovered edges corresponding to the optimal (size $k$) set of vertices. I don't exactly follow your second question. For a set $S \subseteq V$, the number of uncovered edges is equal to the number of edges that have neither end-point in $S$...? $\endgroup$
    – Television
    Feb 19 '19 at 15:28
  • $\begingroup$ So, if the algorithm outputs a set $S$ of vertices, then (i) that set must have size at most $3k$, and (ii) the number of pairs of vertices in $S$ that don't have an edge should be at most three times the number of such pairs of vertices in any set of $k$ vertices? Condition (ii) is strange, as making the set larger makes it harder to cover all the pairs. Indeed, according to these criteria, my algorithm could output the empty set of vertices, which has size at most $3k$ and leaves no pairs of vertices uncovered. $\endgroup$
    – Neal Young
    Feb 20 '19 at 2:34
  • $\begingroup$ @NealYoung Your understanding of the problem is incorrect. The means to judge the quality of your solution is not the number of pairs of vertices that don't have an edge between them. It is the number of edges in the original graph that have neither end point in $S$. So, for instance, if your graph $G$ was a path with $5$ vertices, and your solution outputs the first $3$ points, then the cost of your solution is $1$ since the last edge of $G$ has neither end-point in $S$. $\endgroup$
    – Television
    Feb 20 '19 at 5:36
  • 1
    $\begingroup$ You may want to look at algorithms for partial covering problems. In partial vertex cover the goal is to cover a given number of edges (not necessarily all in the usual vertex cover problem) and there is a constant factor approximation for partial vertex cover and other related problems. link.springer.com/article/10.1007/s00453-009-9317-0 $\endgroup$ Feb 20 '19 at 6:36

Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph $G=(V,E)$ and an integer $m' \le |E|$ and the goal is to find a minimum cardinality subset $S$ of vertices such that they cover at least $m'$ edges. Hence, if $m' = |E|$ we have the usual Vertex Cover problem. A $2$-approximation is known for PVC. To solve the OP's question, if we know the number of edges that are not covered by an optimum solution consisting of $k$ vertices (which we can guess), say $\ell$, we set $m' = |E| - \ell$ and run the approximation algorithm for PVC. We will obtain a set $S \subseteq V$ of cardinalty at most $2k$ such that no more than $\ell$ edges are uncovered.

  • $\begingroup$ Thanks for the reference! You are right, there is no need to go to a bi-criteria setting. Just out of curiosity, is there a terminology for such algorithms, that overshoot the budget by some factor, but provide a solution at least as good as the optimal (in terms of cost)? "Approximation" does not quite seem to capture this phenomenon... $\endgroup$
    – Television
    Feb 21 '19 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.