Faster deterministic Feedback Vertex Set. (English) Zbl 1371.68116
Summary: We present a new deterministic algorithm for the Feedback Vertex Set problem parameterized by the solution size. Our algorithm runs in \(\mathcal O^\ast((2+\phi)^k)\) time, where \(\phi<1.619\) is the golden ratio, surpassing the previously fastest \(\mathcal O^\ast((1+2\sqrt{2})^k)\)-time deterministic algorithm due to Y. Cao et al. [Lect. Notes Comput. Sci. 6139, 93–104 (2010; Zbl 1285.68061)]. In our development we follow the approach of Cao et al. [loc. cit.]; 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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Citations:
Zbl 1285.68061References:
| [1] | Becker, A.; Bar-Yehuda, R.; Geiger, D., Randomized algorithms for the loop cutset problem, J. Artif. Intell. Res., 12, 219-234 (2000) · Zbl 0947.68138 |
| [2] | Bodlaender, H. L., On disjoint cycles, Int. J. Found. Comput. Sci., 5, 1, 59-68 (1994) · Zbl 0803.05030 |
| [3] | Bodlaender, H. L.; Cygan, M.; Kratsch, S.; Nederlof, J., Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, (Fomin, F. V.; Freivalds, R.; Kwiatkowska, M. Z.; Peleg, D., ICALP (1). ICALP (1), Lect. Notes Comput. Sci., vol. 7965 (2013), Springer), 196-207 · Zbl 1296.68074 |
| [4] | Bodlaender, H. L.; van Dijk, T. C., A cubic kernel for feedback vertex set and loop cutset, Theory Comput. Syst., 46, 3, 566-597 (2010) · Zbl 1215.68170 |
| [5] | Burrage, K.; Estivill-Castro, V.; Fellows, M. R.; Langston, M. A.; Mac, S.; Rosamond, F. A., The undirected feedback vertex set problem has a \(poly(k)\) kernel, (Bodlaender, H. L.; Langston, M. A., IWPEC. IWPEC, Lect. Notes Comput. Sci., vol. 4169 (2006), Springer), 192-202 · Zbl 1154.68421 |
| [6] | Cao, Y.; Chen, J.; Liu, Y., On feedback vertex set new measure and new structures, (Kaplan, H., SWAT. SWAT, Lect. Notes Comput. Sci., vol. 6139 (2010), Springer), 93-104 · Zbl 1285.68061 |
| [7] | Chen, J.; Fomin, F. V.; Liu, Y.; Lu, S.; Villanger, Y., Improved algorithms for feedback vertex set problems, J. Comput. Syst. Sci., 74, 7, 1188-1198 (2008) · Zbl 1152.68055 |
| [8] | Chen, J.; Liu, Y.; Lu, S.; O’Sullivan, B.; Razgon, I., A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 5 (2008) · Zbl 1231.68149 |
| [9] | Chitnis, R. H.; Cygan, M.; Hajiaghayi, M. T.; Marx, D., Directed subset feedback vertex set is fixed-parameter tractable, (Czumaj, A.; Mehlhorn, K.; Pitts, A. M.; Wattenhofer, R., ICALP (1). ICALP (1), Lect. Notes Comput. Sci., vol. 7391 (2012), Springer), 230-241 · Zbl 1272.68149 |
| [10] | Cygan, M.; Dell, H.; Lokshtanov, D.; Marx, D.; Nederlof, J.; Okamoto, Y.; Paturi, R.; Saurabh, S.; Wahlström, M., On problems as hard as CNF-SAT, (IEEE Conference on Computational Complexity (2012), IEEE), 74-84 |
| [11] | Cygan, M.; Kratsch, S.; Nederlof, J., Fast hamiltonicity checking via bases of perfect matchings, (Boneh, D.; Rougarden, T.; Feigenbaum, J., STOC (2013), ACM), 301-310 · Zbl 1293.05288 |
| [12] | Cygan, M.; Nederlof, J.; Pilipczuk, M.; Pilipczuk, M.; van Rooij, J. M.M.; Wojtaszczyk, J. O., Solving connectivity problems parameterized by treewidth in single exponential time, (Ostrovsky, R., FOCS (2011), IEEE), 150-159 · Zbl 1292.68122 |
| [13] | Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, J. O., Subset feedback vertex set is fixed-parameter tractable, SIAM J. Discrete Math., 27, 1, 290-309 (2013) · Zbl 1268.05196 |
| [14] | Dehne, F. K.H. A.; Fellows, M. R.; Langston, M. A.; Rosamond, F. A.; Stevens, K., An \(O(2^{O(k)}) n^3\) FPT algorithm for the undirected feedback vertex set problem, Theory Comput. Syst., 41, 3, 479-492 (2007) · Zbl 1148.68037 |
| [15] | Downey, R. G.; Fellows, M. R., Fixed parameter tractability and completeness, (Complexity Theory: Current Research (1992)), 191-225 · Zbl 0768.68136 |
| [16] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [17] | Gabow, H. N.; Stallmann, M. F.M., Efficient algorithms for graphic matroid intersection and parity (extended abstract), (Brauer, W., ICALP. ICALP, Lect. Notes Comput. Sci., vol. 194 (1985), Springer), 210-220 · Zbl 0567.05002 |
| [18] | Guo, J.; Gramm, J.; Hüffner, F.; Niedermeier, R.; Wernicke, S., Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. Syst. Sci., 72, 8, 1386-1396 (2006) · Zbl 1119.68134 |
| [19] | Kanj, I. A.; Pelsmajer, M. J.; Schaefer, M., Parameterized algorithms for feedback vertex set, (Downey, R. G.; Fellows, M. R.; Dehne, F. K.H. A., IWPEC. IWPEC, Lect. Notes Comput. Sci., vol. 3162 (2004), Springer), 235-247 · Zbl 1104.68541 |
| [20] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations. Complexity of Computer Computations, IBM Res. Symp. Ser. (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065 |
| [21] | Kociumaka, T.; Pilipczuk, M., Faster deterministic feedback vertex set (2013) |
| [22] | Oxley, J., Matroid Theory (2011), Oxford University Press · Zbl 1254.05002 |
| [23] | Raman, V.; Saurabh, S.; Subramanian, C. R., Faster fixed parameter tractable algorithms for finding feedback vertex sets, ACM Trans. Algorithms, 2, 3, 403-415 (2006) · Zbl 1321.05275 |
| [24] | Reed, B. A.; Smith, K.; Vetta, A., Finding odd cycle transversals, Oper. Res. Lett., 32, 4, 299-301 (2004) · Zbl 1052.05061 |
| [25] | Thomassé, S., A \(4 k^2\) kernel for feedback vertex set, ACM Trans. Algorithms, 32, 1 (2010) · Zbl 1300.05236 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
