1 Search Results for "Kiesel, Rafael"

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2022.32
PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT

Authors: Rafael Kiesel and André Schidler

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

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.
Cite as

Rafael Kiesel and André Schidler. PACE Solver Description: DAGer - Cutting out Cycles with MaxSAT. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 32:1-32:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.32},
  URN =		{urn:nbn:de:0030-drops-173885},
  doi =		{10.4230/LIPIcs.IPEC.2022.32},
  annote =	{Keywords: Directed Feeback Vertex Set, Data Reductions, Incremental MaxSAT}
}
  • Refine by Author
  • 1 Kiesel, Rafael
  • 1 Schidler, André

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Data Reductions
  • 1 Directed Feeback Vertex Set
  • 1 Incremental MaxSAT

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact