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.30
URN: urn:nbn:de:0030-drops-173861
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17386/
Bergenthal, Moritz ;
Dirks, Jona ;
Freese, Thorben ;
Gahde, Jakob ;
Gerhard, Enna ;
Grobler, Mario ;
Siebertz, Sebastian
PACE Solver Description: GraPA-JAVA
Abstract
We present an exact solver for the DFVS, submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2022. The solver heavily relies on data reduction (known from the literature and new reduction rules). The instances are then further processed by integer linear programming approaches. We implemented the algorithm in the scope of a student project at the University of Bremen.
BibTeX - Entry
@InProceedings{bergenthal_et_al:LIPIcs.IPEC.2022.30,
author = {Bergenthal, Moritz and Dirks, Jona and Freese, Thorben and Gahde, Jakob and Gerhard, Enna and Grobler, Mario and Siebertz, Sebastian},
title = {{PACE Solver Description: GraPA-JAVA}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {30:1--30: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/17386},
URN = {urn:nbn:de:0030-drops-173861},
doi = {10.4230/LIPIcs.IPEC.2022.30},
annote = {Keywords: complexity theory, parameterized complexity, linear programming, java, directed feedback vertex set, PACE 2022}
}
