<p>Here is the proof of Petrank's reduction. This was suggested to me by <a href="http://www.lamsade.dauphine.fr/~bonnet/" rel="noreferrer">Édouard Bonnet</a>. I still do not know whether this can be turned into an L-reduction.</p>

<blockquote>
  <p>Suppose there is a PTAS algorithm $\mathscr{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$.
  We can use $\mathscr{A}$ to solve MIN VERTEX COVER on $G$ by invoking it for $k=1,2,\dots, n$, and keep the best of all the produced solutions. Assume that it is obtained for $k=k_0$.
  We claim that $\mathscr{A}$ for $k=k_0$ produces a solution where $k_0$ vertices cover at least $(1-\varepsilon)m$ edges. Indeed, when $k=opt_{VC}(G)$ (where $opt_{VC}(G)$ denotes the minimum solution size for MIN VERTEX COVER on $G$), at least $(1-\varepsilon)m$ edges must be covered by the result of $\mathscr{A}$. Since the result of $\mathscr{A}$ for $k=k_0$ is at least as good as this, the claim follows.</p>
  
  <p>Thus, at most $\varepsilon \cdot m$ edges are not covered. We construct a set $C$ with the $k_0$ vertices selected by $\mathscr{A}$, to which we add one arbitrary vertex of each of the remaining $\varepsilon \cdot m$ uncovered edges.
  This set $C$ is a vertex cover for $G$, and its size is $k_0 + \varepsilon \cdot m$. 
  However, in a cubic graph, $m \leq 3k_0$ (in any optimal solution for MIN VERTEX COVER, each vertex can cover at most 3 edges). 
  Therefore, $|C| \leq k_0 + \varepsilon \cdot 3k_0 = k_0(1+\varepsilon')$, by setting $\varepsilon' = 3\varepsilon$. This contradicts the APX-hardness of MIN VERTEX COVER on cubic graphs.</p>
</blockquote>

CC BY-SA 3.0
2016-07-08T07:22:20.450Z
2016-07-08T07:22:20.450Z
Florent Foucaud
<p>My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3).</p>

<p><b>MAX k VERTEX COVER</b> (aka MAX k-COVERAGE)<br>
INPUT: a graph $G$, an integer $k$<br>
OUTPUT: a set $C\subseteq V(G)$ of vertices of size $k$<br>
MEASURE: the number of edges of $G$ that have at least one endpoint in $C$</p>

<p>MAX k VERTEX COVER is proved to be APX-hard on subcubic graphs, by a reduction from MIN VERTEX COVER (itself well-known to be APX-hard on subcubic graphs), in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7356" rel="nofollow">this 1994 paper</a> by Petrank (Theorem 5.4). However, the proof is very succinct and in a formalism that I do not know, hence I could not grasp the details of it. I would like to have a formal proof in a more standard language. (For example, a proof that this reduction is an L-reduction would be perfect!)</p>

<blockquote>
  <p><b>Question:</b> Can someone explain the proof of Petrank's reduction (for example in terms of standard L-reductions)? Alternatively, give (or point to) a different reduction with such a proof.</p>
</blockquote>

<hr>

<p><b>Note:</b> in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.1611&amp;rep=rep1&amp;type=pdf" rel="nofollow">Lanberg's 1998 master thesis</a>, a stronger result than Petrank's is proved (the hardness remains valid for a wide range of values of $k$), but only for graphs of maximum degree 30 (see Lemma 3.1). I do not know if other results of APX-hardness for the problem exist in the literature.</p>

<reference-request><graph-algorithms><approximation-hardness><covering-problems>
Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs
Florent Foucaud
# Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

(Asked by: username_0 on 2016-05-27)

My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3).

**MAX k VERTEX COVER** (aka MAX k-COVERAGE)  
INPUT: a graph $G$, an integer $k$  
OUTPUT: a set $C\subseteq V(G)$ of vertices of size $k$  
MEASURE: the number of edges of $G$ that have at least one endpoint in $C$

MAX k VERTEX COVER is proved to be APX-hard on subcubic graphs, by a reduction from MIN VERTEX COVER (itself well-known to be APX-hard on subcubic graphs), in [this 1994 paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7356) by Petrank (Theorem 5.4). However, the proof is very succinct and in a formalism that I do not know, hence I could not grasp the details of it. I would like to have a formal proof in a more standard language. (For example, a proof that this reduction is an L-reduction would be perfect!)

> **Question:** Can someone explain the proof of Petrank's reduction (for example in terms of standard L-reductions)? Alternatively, give (or point to) a different reduction with such a proof.

---

**Note:** in [Lanberg's 1998 master thesis](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.1611&rep=rep1&type=pdf), a stronger result than Petrank's is proved (the hardness remains valid for a wide range of values of $k$), but only for graphs of maximum degree 30 (see Lemma 3.1). I do not know if other results of APX-hardness for the problem exist in the literature.

**Tags:** reference-request, graph-algorithms, approximation-hardness, covering-problems


---

## 1 answers

### Answer by username_0 on 2016-07-08. Score: 5

Here is the proof of Petrank's reduction. This was suggested to me by [Édouard Bonnet](http://www.lamsade.dauphine.fr/~bonnet/). I still do not know whether this can be turned into an L-reduction.

> Suppose there is a PTAS algorithm $\mathscr{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$.
> We can use $\mathscr{A}$ to solve MIN VERTEX COVER on $G$ by invoking it for $k=1,2,\dots, n$, and keep the best of all the produced solutions. Assume that it is obtained for $k=k\_0$.
> We claim that $\mathscr{A}$ for $k=k\_0$ produces a solution where $k\_0$ vertices cover at least $(1-\varepsilon)m$ edges. Indeed, when $k=opt\_{VC}(G)$ (where $opt\_{VC}(G)$ denotes the minimum solution size for MIN VERTEX COVER on $G$), at least $(1-\varepsilon)m$ edges must be covered by the result of $\mathscr{A}$. Since the result of $\mathscr{A}$ for $k=k\_0$ is at least as good as this, the claim follows.
>
> Thus, at most $\varepsilon \cdot m$ edges are not covered. We construct a set $C$ with the $k\_0$ vertices selected by $\mathscr{A}$, to which we add one arbitrary vertex of each of the remaining $\varepsilon \cdot m$ uncovered edges.
> This set $C$ is a vertex cover for $G$, and its size is $k\_0 + \varepsilon \cdot m$.
> However, in a cubic graph, $m \leq 3k\_0$ (in any optimal solution for MIN VERTEX COVER, each vertex can cover at most 3 edges).
> Therefore, $|C| \leq k\_0 + \varepsilon \cdot 3k\_0 = k\_0(1+\varepsilon')$, by setting $\varepsilon' = 3\varepsilon$. This contradicts the APX-hardness of MIN VERTEX COVER on cubic graphs.


---

