4
$\begingroup$

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?

$\endgroup$
6

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.