Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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).
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$.
