Reduce Vertex Cover with size k to Vertex Cover with size n/2
For $k&lt;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&gt;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.