Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

Question

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

Answer 1

Here is the proof of Petrank's reduction. This was suggested to me by Édouard 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.