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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.