


























We present two new deterministic algorithms for the Feedback Vertex Set problem parameterized by the solution size. We begin with a simple algorithm, which runs in O*((2 + φ)^k) time, where φ< 1.619 is the golden ratio. It already surpasses the previously fastest O*((1+2sqrt(2))^k)-time deterministic algorithm due to Cao et al. [SWAT 2010]. In our developments 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. Then, we present a modification of the algorithm which, using a more involved set of branching rules, achieves O*(3.592^k) running time.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。