# Bi-criteria combinatorial approximation algorithms for min k-vertex cover

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$$.

• @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$...? – Television Feb 19 '19 at 15:28
• 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. – Neal Young Feb 20 '19 at 2:34
• @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$. – Television Feb 20 '19 at 5:36
• 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 – Chandra Chekuri 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.