# Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:

• $k = n/2$: This case is trivial.
• $k > n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
• $k < n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.

• After NT reduction (it’s polynomial), a graph has a vertex cover of size at least $\frac{n}{2}$. – Eugene Apr 9 '18 at 21:50
• What's $k$? The target size in the Vertex Cover problem? – David Richerby Apr 10 '18 at 14:59

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.

For k < n/2, add enough vertices with a single edge out of them (pointing back at themselves) such that the size of the new vertex cover is half the size of the new graph.

For k > n/2, add enough vertices connected to an arbitrary vertex already in the vertex cover such that the size of the original vertex cover is half the size of the new graph.

• "an arbitrary vertex already in the vertex cover" -- we don't know which vertices make up a vertex cover yet. Just adding isolated vertices works. Also, if self-edges are disallowed, then for the k < n/2 case you can add triangles. 2 out of 3 vertices in each triangle must be chosen, so it's always possible to add enough triangles to bring the total k required up to n/2. – j_random_hacker Jan 10 '18 at 12:04