Document Open Access Logo

Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

Authors Sebastian Angrick, Ben Bals, Katrin Casel , Sarel Cohen , Tobias Friedrich , Niko Hastrich , Theresa Hradilak, Davis Issac , Otto Kißig , Jonas Schmidt, Leo Wendt

PDF
Thumbnail PDF

File

LIPIcs.SEA.2023.10.pdf
  • Filesize: 1.59 MB
  • 14 pages

Document Identifiers

Author Details

Sebastian Angrick
  • Hasso Plattner Institute, Universität Potsdam, Germany
Ben Bals
  • Hasso Plattner Institute, Universität Potsdam, Germany
Katrin Casel
  • Humboldt-Universität zu Berlin, Germany
Sarel Cohen
  • The Academic College of Tel Aviv-Yaffo, Israel
Tobias Friedrich
  • Hasso Plattner Institute, Universität Potsdam, Germany
Niko Hastrich
  • Hasso Plattner Institute, Universität Potsdam, Germany
Theresa Hradilak
  • Hasso Plattner Institute, Universität Potsdam, Germany
Davis Issac
  • Hasso Plattner Institute, Universität Potsdam, Germany
Otto Kißig
  • Hasso Plattner Institute, Universität Potsdam, Germany
Jonas Schmidt
  • Hasso Plattner Institute, Universität Potsdam, Germany
Leo Wendt
  • Hasso Plattner Institute, Universität Potsdam, Germany

Cite As Get BibTex

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SEA.2023.10

Abstract

In the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • directed feedback vertex set
  • vertex cover
  • reduction rules

Metrics

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

Supplementary Materials

References

  1. Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609:211-225, 2016. Google Scholar
  2. Ali Baharev, Hermann Schichl, Arnold Neumaier, and Tobias Achterberg. An exact method for the minimum feedback arc set problem. ACM Journal of Experimental Algorithmics, 26:1.4:1-1.4:28, 2021. URL: https://doi.org/10.1145/3446429.
  3. Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020. In Proceedings of the SAT Competition 2020 - Solver and Benchmark Descriptions, volume B-2020-1, pages 51-53, 2020. Google Scholar
  4. Shaowei Cai, Kaile Su, Chuan Luo, and Abdul Sattar. NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover. Journal of Artificial Intelligence Research, 46:687-716, 2013. URL: https://doi.org/10.1613/jair.3907.
  5. Srimat T Chakradhar, Arun Balakrishnan, and Vishwani D Agrawal. An exact algorithm for selecting partial scan flip-flops. Journal of Electronic Testing, 7(1):83-93, 1995. Google Scholar
  6. Jianer Chen, Iyad A Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40-42):3736-3756, 2010. Google Scholar
  7. Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem. Journal of the ACM, 55:21:1-21:19, 2008. Google Scholar
  8. 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
  9. Reinhard Diestel. Graph Theory 3rd ed. Graduate Texts in Mathematics, 173, 2005. Google Scholar
  10. M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper). In International Symposium on Parameterized and Exact Computation (IPEC), volume 148, pages 25:1-25:23, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.25.
  11. Paul Erdős and Alfréd Rényi. On random graphs. Publicationes Mathematicae, 6:290-297, 1959. Google Scholar
  12. Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  13. Rudolf Fleischer, Xi Wu, and Liwei Yuan. Experimental study of fpt algorithms for the directed feedback vertex set problem. In European Symposium on Algorithms (ESA), pages 611-622. Springer, 2009. Google Scholar
  14. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A Measure & Conquer Approach for the Analysis of Exact Algorithms. Journal of the ACM, 56(5):25:1-25:32, 2009. URL: https://doi.org/10.1145/1552285.1552286.
  15. Philippe Galinier, Eunice Lemamou, and Mohamed Wassim Bouzidi. Applying local search to the feedback vertex set problem. Journal of Heuristics, 19(5):797-818, 2013. Google Scholar
  16. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL: https://www.gurobi.com.
  17. David G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. CoRR, abs/2205.08022, 2022. URL: https://doi.org/10.48550/arXiv.2205.08022.
  18. Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. WeGotYouCovered: The winning solver from the PACE 2019 challenge, vertex cover track. In Proceedings of the SIAM Workshop on Combinatorial Scientific Computing (CSC), pages 1-11, 2020. URL: https://doi.org/10.1137/1.9781611976229.1.
  19. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  20. Rafael Kiesel and André Schidler. A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets. In Gonzalo Navarro and Julian Shun, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 39-52. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977561.ch4.
  21. D.H. Lee and S.M. Reddy. On determining scan flip-flops in partial-scan designs. In IEEE/ACM International Conference on Computer-Aided Design, (ICCAD), pages 322-325, 1990. URL: https://doi.org/10.1109/ICCAD.1990.129914.
  22. Mile Lemaic. Markov-Chain-Based Heuristics for the Feedback Vertex Set Problem for Digraphs. PhD thesis, Universität zu Köln, 2008. URL: https://kups.ub.uni-koeln.de/2547/1/Dissertation.pdf.
  23. Hen-Ming Lin and Jing-Yang Jou. Computing minimum feedback vertex sets by contraction operations and its applications on cad. In Proceedings of the IEEE International Conference On Computer Design, VLSI in Computers and Processors, (ICCD), pages 364-369. IEEE, 1999. Google Scholar
  24. Daniel Lokshtanov, NS Narayanaswamy, Venkatesh Raman, MS Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG), 11(2):1-31, 2014. Google Scholar
  25. Tatiana Orenstein, Zvi Kohavi, and Irith Pomeranz. An optimal algorithm for cycle breaking in directed graphs. Journal of Electronic Testing, 7(1):71-81, 1995. Google Scholar
  26. Panos M Pardalos, Tianbing Qian, and Mauricio GC Resende. A greedy randomized adaptive search procedure for the feedback vertex set problem. Journal of Combinatorial Optimization, 2(4):399-412, 1998. Google Scholar
  27. Rick Plachetta and Alexander van der Grinten. Sat-and-reduce for vertex cover: Accelerating branch-and-reduce by sat solving. In Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 169-180, 2021. URL: https://doi.org/10.1137/1.9781611976472.13.
  28. Igor Razgon. Computing minimum directed feedback vertex set in O(1.9977^n). In Italian Conference on Theoretical Computer Science (ICTCS), pages 70-81. World Scientific, 2007. Google Scholar
  29. Andreas Schindler and Rafael Kiesel. Dager. URL: https://github.com/ASchidler/dfvs.
  30. Christian Schulz, Ernestine Großmann, Tobias Heuer, and Darren Strash. Pace 2022: Directed feedback vertex set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), 2022. Google Scholar
  31. Adi Shamir. A linear time algorithm for finding minimum cutsets in reducible graphs. SIAM Journal on Computing, 8(4):645-655, 1979. Google Scholar
  32. G Smith and R Walford. The identification of a minimal feedback vertex set of a directed graph. IEEE Transactions on Circuits and Systems, 22(1):9-15, 1975. Google Scholar
  33. Matthias F Stallmann, Yang Ho, and Timothy D Goodrich. Graph profiling for vertex cover: Targeted reductions in a branch and reduce solver. arXiv preprint arXiv:2003.06639, 2020. Google Scholar
  34. Ching-Chy Wang, Errol L Lloyd, and Mary Lou Soffa. Feedback vertex sets and cyclically reducible graphs. Journal of the ACM, 32(2):296-313, 1985. Google Scholar
  35. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Information and Computation, 255:126-146, 2017. URL: https://doi.org/10.1016/j.ic.2017.06.001.
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 About DROPS Imprint Privacy Contact