| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428516 | Information Processing Letters | 2014 | 5 Pages |
•Faster deterministic FPT algorithm for Feedback Vertex Set.•Reinterpretation and simplification of the previously best algorithm for FVS.•Simpler proof that FVS becomes polynomial-time solvable in subcubic graphs.
We present a new deterministic algorithm for the Feedback Vertex Set problem parameterized by the solution size. Our algorithm runs in O⁎((2+ϕ)k)O⁎((2+ϕ)k) time, where ϕ<1.619ϕ<1.619 is the golden ratio, surpassing the previously fastest O⁎((1+22)k)-time deterministic algorithm due to Cao et al. (2010) [6]. In our development we follow the approach of Cao et al.; however, thanks to a new reduction rule, we obtain not only better dependency on the parameter in the running time, but also a solution with simple analysis and only a single branching rule.
