Reducing the vertex cover problem to a variation of the vertex cover problem
One note is that you'll have to use $k$ in your transformation.



Here's one approach that I think works:

We want some $G' = (V', E')$ that has a vertex cover of size $\le \frac{|V'|}{4}$ iff $G$ has a vertex cover of size $\le k$.

If $k = \frac{|V|}{4}$, just set $G' = G$.

When $k \neq \frac{|V|}{4}$, one idea is to add a disconnected graph $H$ to $G$, where we know the vertex cover size of $H$.

Case 1: $k &gt; \frac{|V|}{4}$. Then we want to add a graph with a small vertex cover. A star graph should do it. A star graph $H$ with $m$ vertices has vertex cover size $1$.

Set $G' = G \cup H$, a graph with $|V| + m$ vertices. It has vertex cover of size $\le k+1$ iff $G$ has a vertex cover of size $\le k$.

What should $m$ be? Let's solve

$$\frac{k + 1}{|V| + m} = \frac{1}{4}$$

This gives $m = 4(k+1)-|V|$. So when $k &gt; \frac{|V|}{4}$, add a disconnected $[4(k+1)-|V|]$-vertex star graph to $G$, and call the $\frac{|V|}{4}$ vertex cover algorithm on that. $\square$

Case 2: $k &lt; \frac{|V|}{4}$, we can add a complete graph with some properly chosen number $m$ vertices*. Will leave it at that.

*In this case when you solve for $m$, $m$ may not always be an integer; this can be dealt with by adding a $\lceil m \rceil$-vertex complete graph, which "overshoots" a bit, and then adding a small star graph

[Let me know for further clarification/etc]