Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.32
URN: urn:nbn:de:0030-drops-173885
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17388/
Kiesel, Rafael ; Schidler, André
PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT
| pdf-format: |
|
Abstract
We describe the solver DAGer for the Directed Feedback Vertex Set (DFVS) problem, as it was submitted to the exact track of the 2022 PACE Challenge. Our approach first applies a wide range of preprocessing techniques involving both well-known data reductions for DFVS as well as non-trivial adaptations from the vertex cover problem. For the actual solving, we found that using a MaxSAT solver with incremental constraints achieves a good performance.
BibTeX - Entry
@InProceedings{kiesel_et_al:LIPIcs.IPEC.2022.32,
author = {Kiesel, Rafael and Schidler, Andr\'{e}},
title = {{PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {32:1--32: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/17388},
URN = {urn:nbn:de:0030-drops-173885},
doi = {10.4230/LIPIcs.IPEC.2022.32},
annote = {Keywords: Directed Feeback Vertex Set, Data Reductions, Incremental MaxSAT}
}
| Keywords: | Directed Feeback Vertex Set, Data Reductions, Incremental MaxSAT | |
| Seminar: | 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 | |
| Supplementary Material: |
Software (Source Code): https://github.com/ASchidler/dfvs Software (Source Code): https://doi.org/10.5281/zenodo.6627405 |
