# FPT algorithm for a variant of Feedback Vertex Set

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

For an undirected graph $$G$$ and $$k\in \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 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

I believe that the best method to solve this question is to alternate the graph in a way that we randomly choose a vertex from the graph, and with a probability of $$\frac{1}{4}$$, it will be in the solution group. Section 5.1 from this book presents this idea, but I can't seem to alter the graph so that choosing a random vertex will yield the desired probability.

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

• – D.W.
Jul 10 '21 at 22:33
• Where did you encounter this problem? Can you credit the original source? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
Jul 10 '21 at 22:47
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
Jul 10 '21 at 22:47
• – D.W.
Jul 10 '21 at 22:48
• Thank you for the comment. Please note that I am not responsible for the other questions about this topic and that none of those questions are descriptive and answer the guide for asking a good homework question. I added another method I tried in solving this question, At this point, I am not sure if this question is even answerable. Jul 13 '21 at 15:55