<p>Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph <span class="math-container">$G=(V,E)$</span> and an integer <span class="math-container">$m' \le |E|$</span> and the goal is to find a minimum cardinality subset <span class="math-container">$S$</span> of vertices such that they cover at least <span class="math-container">$m'$</span> edges. Hence, if <span class="math-container">$m' = |E|$</span> we have the usual Vertex Cover problem. A <span class="math-container">$2$</span>-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 <span class="math-container">$k$</span> vertices (which we can guess), say <span class="math-container">$\ell$</span>, we set <span class="math-container">$m' = |E| - \ell$</span> and run the approximation algorithm for PVC. We will obtain a set <span class="math-container">$S \subseteq V$</span> of cardinalty at most <span class="math-container">$2k$</span> such that no more than <span class="math-container">$\ell$</span> edges are uncovered.  </p>

CC BY-SA 4.0
2019-02-21T15:47:26.650Z
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...
Television
CC BY-SA 4.0
2019-02-20T14:27:27.713Z
2019-02-20T14:27:27.713Z
Chandra Chekuri
<p><strong>Min k-vertex cover</strong>: Given a graph <span class="math-container">$G = (V,E)$</span>, the goal of the min k-vertex cover problem is to output <span class="math-container">$k$</span> vertices from <span class="math-container">$V$</span> such that the number of uncovered edges in <span class="math-container">$E$</span> is minimized.</p>

<p>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 <span class="math-container">$(3,3)$</span> bi-criteria approximation.</p>

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

<p>Clarification: The objective of this problem is to output a set of vertices <span class="math-container">$S$</span> that minimize the <strong>number of uncovered edges in <span class="math-container">$G = (V,E)$</span></strong>. The number of uncovered edges is equal to the number of edges in <span class="math-container">$E$</span> that have neither end point in <span class="math-container">$S$</span>.</p>

CC BY-SA 4.0
2019-02-19T15:28:11.620Z
@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
CC BY-SA 4.0
2019-02-20T02:34:12.867Z
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
CC BY-SA 4.0
2019-02-20T05:36:27.997Z
@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
CC BY-SA 4.0
2019-02-20T06:36:24.163Z
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. https://link.springer.com/article/10.1007/s00453-009-9317-0
Chandra Chekuri
<approximation>
Bi-criteria combinatorial approximation algorithms for min k-vertex cover
Television
# Bi-criteria combinatorial approximation algorithms for min k-vertex cover

(Asked by: username_0 on 2019-02-18)

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

**Tags:** approximation
> **Comments:**
> **username_0**: @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$...?  
> **username_1**: 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.  
> **username_0**: @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$.  
> **username_2**: 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. https://link.springer.com/article/10.1007/s00453-009-9317-0  

---

## 1 answers

### Answer by username_2 on 2019-02-20. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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...  

---

