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

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.


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.