License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.28
URN: urn:nbn:de:0030-drops-173847
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17384/
Angrick, Sebastian ;
Bals, Ben ;
Casel, Katrin ;
Cohen, Sarel ;
Friedrich, Tobias ;
Hastrich, Niko ;
Hradilak, Theresa ;
Issac, Davis ;
Kißig, Otto ;
Schmidt, Jonas ;
Wendt, Leo
PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set
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.
BibTeX - Entry
@InProceedings{angrick_et_al:LIPIcs.IPEC.2022.28,
author = {Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
title = {{PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {28:1--28:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17384},
URN = {urn:nbn:de:0030-drops-173847},
doi = {10.4230/LIPIcs.IPEC.2022.28},
annote = {Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
