# #StackBounty: #algorithms #randomized-algorithms #parameterized-complexity FPT algorithm for a variant of Feedback Vertex Set

### Bounty: 50

I am interested in a variant of the Feedback Vertex Set (FVS) problem.

For an undirected graph $$G$$ and $$kin mathbb{N}$$ we need to decide if there is a subset $$S subseteq V(G)$$ of size at most $$k$$ s.t every connected component in $$G-S$$ is a cycle or a tree.

I am trying to solve this problem and find an FPT algorithm with a time complexity of $$4^{k}n^{O(1)}$$.

I tried using known methods for solving the FVS problems using branching and iterative compression method but the time complexity is larger, $$(3k)^{k}$$ for the branching algorithms and $$5^{k}$$ for the iterative compressions method, and I couldn’t reduce it by changing the rules.
I took the methods from here

Is it even possible? Maybe there is a randomized version for this problem?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.