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.32
URN: urn:nbn:de:0030-drops-173885
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17388/
Go to the corresponding LIPIcs Volume Portal

Kiesel, Rafael ; Schidler, André

PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT

pdf-format:
LIPIcs-IPEC-2022-32.pdf (0.6 MB)

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
Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI