# algorithms – reduction for FVS with cycle

problem : for given an undirected graph G and k ∈ N, and the objective is to decide whether there exists a subset X ⊆ V (G) of size at most k such that every connected component in G − X is either a tree or a cycle.

would like to know if I could construct reduction to the graph , that would return new graph G’ such that all his vertex are of degree $$>=3$$ ,

I have algorithm to construct this to FVS :

• Rule 1: if there exist a vertex with self-loop, delete and decrease k by 1
• Rule 2: if there exist a vertex of degree <=1 ,delete v
• Rule 3 : if there exist a vertex v of degree 2 delete v and connect its neighbors

thanks a lot