I know that feedback vertex set (FVS) problem is $mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS.

Specifically, given a undirected graph $G$, we construct $G’$ as follow:

- For every $uv in E(G)$, we construct a new vertex $e_{uv}$, and let $V_{0} = { e_{uv} : uv in E(G) }$.
- Let $V(G’) = V(G) cup V_{0}$
- An edge is in $E(G’)$ if it is in $E(G)$ or one of its endpoint is the vertex $e_{uv} in V_{0}$ and another endpoint of it is the endpoint of $e_{uv}$. Namely, $E(G’) = E(G) cup { ue_{uv}, ve_{uv} : e_{uv} in V_{0} }$.

It is easy to see that $G$ has a vertex cover of size at most $k$ iff $G’$ has a feedback vertex set of size at most $k$.

Of course, there is a polytime reduction from FVS to VC. I want to know whether there is a reduction with a simple construction. And I hope that the size of the vertex cover and the size of feedback vertex set are equalent, if possible.