# Is there any polytime reduction from feedback vertex set to vertex cover?

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:

1. For every $$uv in E(G)$$, we construct a new vertex $$e_{uv}$$, and let $$V_{0} = { e_{uv} : uv in E(G) }$$.
2. Let $$V(G’) = V(G) cup V_{0}$$
3. 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.

Posted on Categories Articles