<p>I found the solution, it is also mentioned in the <a href="https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf" rel="nofollow noreferrer">book</a> in chapter 4.1.</p>

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

<p>Thus each step takes <span class="math-container">$5^kpoly(n)$</span> time and we do <span class="math-container">$n$</span> iterations.</p>

CC BY-SA 4.0
2019-02-16T20:42:07.573Z
2019-02-16T20:42:07.573Z
yassin
<p>I understand that Disjoint Feedback Vertex Set (= looking for a solution <span class="math-container">$X$</span> of size <span class="math-container">$k$</span> given a solution <span class="math-container">$W$</span> of size <span class="math-container">$k+1$</span> s.t. <span class="math-container">$X \subseteq V \setminus W$</span> ) can be solved in time <span class="math-container">$4^k poly(n)$</span>, see 4.3 <a href="https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf" rel="nofollow noreferrer">here</a>.</p>

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

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

<fixed-parameter-tractable>
Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?
yassin
# Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

(Asked by: username_0 on 2019-02-15)

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](https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf).

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?

**Tags:** fixed-parameter-tractable

---

## 1 answers

### Answer by username_0 on 2019-02-16. Score: 3 | Accepted answer

I found the solution, it is also mentioned in the [book](https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf) 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.


---

