Reducing Vertex Cover to Half Vertex Cover
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| &lt; 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| &gt; 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.
$$