3
$\begingroup$

I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see 4.3 here.

They also say FVS can be solved in $5^k poly(n)$ using iterative compression with the DFVS algorithm, but I can't see how. If I start with a $2$-approximation, the total runtime would be $5^{2k} poly(n)$ by iterating over all subsets of a given solution as $W$ and executing the DFVS algorithm for each.

What is the starting point for the iterative compression and how does it lead to the given runtime?

$\endgroup$
3
$\begingroup$

I found the solution, it is also mentioned in the book in chapter 4.1.

We start by taking a subgraph with $k+1$ arbitrary vertices instead of the whole graph, so the whole vertex set is a $k+1$-solution. Then we do DFVS with every subset to obtain a $k$-solution. Finally we add another vertex from the original graph to our current subgraph (and current solution) and repeat.

Thus each step takes $5^kpoly(n)$ time and we do $n$ iterations.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.