Document Open Access Logo

Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set

Authors Krzysztof Kiljan, Marcin Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.12.pdf
  • Filesize: 394 kB
  • 12 pages

Document Identifiers

Author Details

Krzysztof Kiljan
  • Institute of Informatics, University of Warsaw, Poland
Marcin Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland

Funding

Supported by the "Recent trends in kernelization: theory and experimental evaluation" project, carried out within the Homing programme of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund.

Cite AsGet BibTex

Krzysztof Kiljan and Marcin Pilipczuk. Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.12

Abstract

Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of view of parameterized algorithms and fixed-parameter tractability, Feedback Vertex Set is one of the landmark problems: a long line of study resulted in multiple algorithmic approaches and deep understanding of the combinatorics of the problem. Because of its central role in parameterized complexity, the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured Feedback Vertex Set as the problem of choice in one of its tracks. The results of PACE 2016 on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. In this paper we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Empirical Evaluation of Algorithms
  • Feedback Vertex Set

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Recent trends in kernelization: theory and experimental evaluation - project website, 2018. URL: http://kernelization-experiments.mimuw.edu.pl.
  2. Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609:211-225, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.09.023.
  3. Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. (JAIR), 12:219-234, 2000. URL: http://www.cs.washington.edu/research/jair/abstracts/becker00a.html.
  4. Hans L. Bodlaender. On disjoint cycles. Int. J. Found. Comput. Sci., 5(1):59-68, 1994. Google Scholar
  5. Hans L. Bodlaender and Thomas C. van Dijk. A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst., 46(3):566-597, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9234-2.
  6. Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond. The undirected feedback vertex set problem has a poly(k) kernel. In Hans L. Bodlaender and Michael A. Langston, editors, IWPEC, volume 4169 of Lecture Notes in Computer Science, pages 192-202. Springer, 2006. URL: http://dx.doi.org/10.1007/11847250_18.
  7. Yixin Cao. A naive algorithm for feedback vertex set. In Raimund Seidel, editor, 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA, volume 61 of OASICS, pages 1:1-1:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/OASIcs.SOSA.2018.1.
  8. Yixin Cao, Jianer Chen, and Yang Liu. On feedback vertex set new measure and new structures. In Haim Kaplan, editor, SWAT, volume 6139 of Lecture Notes in Computer Science, pages 93-104. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13731-0_10.
  9. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci., 74(7):1188-1198, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2008.05.002.
  10. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  11. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Rafail Ostrovsky, editor, FOCS, pages 150-159. IEEE, 2011. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120, URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  12. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An O(2^o(k)) n³ FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst., 41(3):479-492, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1345-z.
  13. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The First Parameterized Algorithms and Computational Experiments Challenge. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.30.
  14. Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.30.
  15. Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness. In Complexity Theory: Current Research, pages 191-225, 1992. Google Scholar
  16. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 1999. Google Scholar
  17. Harold N. Gabow and Matthias F. M. Stallmann. An augmenting path algorithm for linear matroid parity. Combinatorica, 6(2):123-150, 1986. URL: http://dx.doi.org/10.1007/BF02579169.
  18. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci., 72(8):1386-1396, 2006. Google Scholar
  19. Kensuke Imanishi and Yoichi Iwata. Feedback Vertex Set solver, entry to PACE 2016, 2016. http://github.com/wata-orz/fvs. Google Scholar
  20. Yoichi Iwata. Linear-time kernelization for feedback vertex set. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 68:1-68:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.68.
  21. Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput., 45(4):1377-1411, 2016. URL: http://dx.doi.org/10.1137/140962838.
  22. Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. Linear-time FPT algorithms via half-integral non-returning a-path packing. CoRR, abs/1704.02700, 2017. URL: http://arxiv.org/abs/1704.02700.
  23. Iyad A. Kanj, Michael J. Pelsmajer, and Marcus Schaefer. Parameterized algorithms for feedback vertex set. In Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne, editors, IWPEC, volume 3162 of Lecture Notes in Computer Science, pages 235-247. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28639-4_21.
  24. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: http://www.cs.berkeley.edu/$\sim$luca/cs172/karp.pdf.
  25. Krzysztof Kiljan and Marcin Pilipczuk. Experimental evaluation of parameterized algorithms for Feedback Vertex Set: code repository, 2018. https://bitbucket.org/marcin_pilipczuk/fvs-experiments. Google Scholar
  26. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. URL: http://dx.doi.org/10.1016/j.ipl.2014.05.001.
  27. Christian Komusiewicz. PACE 2016: tests for Feedback Vertex Set, 2016. https://github.com/ckomus/PACE-fvs. Google Scholar
  28. Marcin Pilipczuk. Feedback Vertex Set solver, entry to PACE 2016, 2016. http://bitbucket.com/marcin_pilipczuk/fvs-pace-challenge. Google Scholar
  29. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms, 2(3):403-415, 2006. Google Scholar
  30. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, 6(2):32:1-32:8, 2010. URL: http://dx.doi.org/10.1145/1721837.1721848.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact