Abstract | ||
---|---|---|
In the Feedback Vertex Set problem, one is given an undirected graph G and an integer k, and one needs to determine whether there exists a set of k vertices that intersects all cycles of G (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent test bed for many important algorithmic techniques in the field such as Iterative Compression [Guo et al. (JCSS'06)], Randomized Branching [Becker et al. (J. Artif. Intell. Res'00)] and Cut&Count [Cygan et al. (FOCS'11)]. In particular, there has been a long race for the smallest dependence f(k) in run times of the type O*(f(k)), where the O* notation omits factors polynomial in n. This race seemed to be run in 2011, when a randomized O*(3k) time algorithm based on Cut&Count was introduced.
In this work, we show the contrary and give a O*(2.7k) time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size k of bounded average degree, a tree decomposition of width (1 − Ω(1))k can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from [Becker et al. (J. Artif. Intell. Res'00)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.
|
Year | DOI | Venue |
---|---|---|
2020 | 10.5555/3381089.3381147 | SODA '20: ACM-SIAM Symposium on Discrete Algorithms
Salt Lake City
Utah
January, 2020 |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jason Li | 1 | 217 | 24.45 |
Jesper Nederlof | 2 | 294 | 24.22 |