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