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.
Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs
reference request;graph algorithms;approximation hardness;covering problems