# Reducing Vertex Cover to Half Vertex Cover

I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $$G = (V,E)$$ and an integer $$k$$, is there a subset of $$V$$ of size $$k$$ which intersects all edges?

Half Vertex Cover: Given a graph $$G = (V,E)$$ and an integer $$k$$, is there a subset of $$V$$ of size $$k$$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).

• We're not here to do your homework! – Yuval Filmus Apr 11 at 16:01
• However, in this case it seems that the exercise is not straightforward. – Yuval Filmus Apr 11 at 17:11

Let special vertex cover be the special case of vertex cover in which $$|V| = 2k+1$$. We later reduce vertex cover to special vertex cover.

Now suppose we're given an instance $$G = (V,E),k$$ of special vertex cover. Construct an instance $$G',k$$ of half vertex cover by attaching $$|E|$$ new edges to each vertex in $$V$$.

The total number of edges in the new graph is $$|E|(|V| + 1)$$. A vertex cover of size $$k$$ in the original graph covers this many edges in the new graph: $$|E|(1+k) = |E|\left(1 + \frac{|V|-1}{2}\right) = |E| \frac{|V| + 1}{2},$$ exactly half the edges. Conversely, consider any $$k$$ vertices of the new graph, which cover exactly half of the edges. If they cover $$m$$ of the original edges then they cover at most $$m + k|E|$$ edges of $$G'$$, where $$m \leq |E|$$. The calculation above shows that $$m = |E|$$, that is, all edges of $$G$$ are covered.

It remains to reduce vertex cover to its special case. If $$|V| = 2k+1$$ then there is nothing to do.

If $$|V| < 2k+1$$, then we add $$\delta := 2k+1 - |V|$$ many paths of length 2 edges. The new graph $$G'=(V',E')$$ has a vertex cover of size $$k' = k + \delta$$ iff the original graph had a vertex cover of size $$k$$. Note that $$|V'|-2k' = (|V| + 3\delta) - 2(k+\delta) = |V| - 2k + \delta = 1.$$

Similarly, if $$|V| > 2k+1$$ then we add $$\delta := |V| - (2k+1)$$ many triangles. The new graph $$G'=(V',E')$$ has a vertex cover of size $$k' = k + 2\delta$$ iff the original graph had a vertex cover of size $$k$$. Note that $$|V'|-2k' = (|V| + 3\delta) - 2(k+2\delta) = |V| - 2k - \delta = 1.$$

In addition to the reduction given by Yuval Filmus, you can also use the following reduction, which avoids blowing up the size of $$G$$ to $$\Theta(|V| \cdot |E|)$$.

Assume w.l.o.g. that $$k<|V|$$ (otherwise the reduction is trivial) and that the instance (graph) $$G = (V,E)$$ of vertex-cover contains a vertex $$v \in V$$ of degree $$1$$ (otherwise you could append a path of length $$2$$ to any vertex and increase $$k$$ by $$1$$).

To obtain an instance $$G'$$ of half-cover attach to $$v$$ $$|E|$$ new edges (towards new nodes), so that $$G'$$ has $$2|E|$$ edges.

If there is a vertex cover of size $$k$$ in $$G$$, then there is also a vertex cover $$C$$ of size $$k$$ that does not include $$v$$. Then, $$C$$ intersects $$|E|$$ edges in both $$G$$ and $$G'$$, i.e., half the edges of $$G'$$.

On the converse, if there is a half-cover $$C'$$ of size $$k$$ for $$G'$$ then $$v \not\in C$$ (since the degree of $$v$$ is $$|E|+1$$), and hence $$C' \subseteq V$$ covers all $$\frac{2|E|}{2} = |E|$$ edges in $$E$$.