#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!!!

Leave a Reply

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