LIPIcs.IPEC.2022.28.pdf
- Filesize: 474 kB
- 4 pages
Document
PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set
Authors
Katrin Casel 
,
Sarel Cohen ,
Tobias Friedrich ,
Davis Issac ,
Otto Kißig ,
-
Part of:
Volume:
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
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. PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.28
Abstract
In this document we describe the techniques we used and implemented for our submission to the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2022. The given problem is Directed Feedback Vertex Set (DFVS), where one is given a directed graph G = (V,E) and wants to find a minimum S ⊆ V such that G-S is acyclic. We approach this problem by first exhaustively applying a set of reduction rules. In order to find a minimum DFVS on the remaining instance, we create and solve a series of Vertex Cover instances.
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)
0PDF Downloads
Supplementary Materials
- Software (Source Code) https://doi.org/10.5281/zenodo.6645235
-
Software (Source Code)
https://github.com/BenBals/mount-doom/tree/exact
browse
archived version
References
-
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.
-
Reinhard Diestel. Graph Theory 3rd ed. Graduate Texts in Mathematics, 173, 2005.
-
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.
-
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.
-
Mile Lemaic. Markov-Chain-Based Heuristics for the Feedback Vertex Set Problem for Digraphs. PhD thesis, Universität zu Köln, 2008.
-
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.