Record link: 
http://hdl.handle.net/20.500.12708/146161
-
Title: 
PACE Solver Description: DAGer – Cutting out Cycles with MaxSAT
en
Citation: 
Kiesel, R., & Schidler, A. (2022). PACE Solver Description: DAGer – Cutting out Cycles with MaxSAT. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Germany. https://doi.org/10.4230/LIPIcs.IPEC.2022.32
-
Publisher DOI: 
10.4230/LIPIcs.IPEC.2022.32
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Kiesel, Rafael 
Schidler, André 
-
Organisational Unit: 
E192 - Institut für Logic and Computation 
-
Published in: 
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) 
-
Date (published): 
1-Dec-2022
-
Event name: 
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) 
en
Event date: 
7-Sep-2022 - 9-Sep-2022
-
Event place: 
Germany
-
Number of Pages: 
4
-
Peer reviewed: 
Yes
-
Keywords: 
Data Reductions; Directed Feeback Vertex Set; Incremental MaxSAT
en
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.
en
Link (external): 
https://drops.dagstuhl.de/opus/volltexte/2022/17388/pdf/LIPIcs-IPEC-2022-32.pdf
http://fpt.wikidot.com/ipec
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

57
checked on Dec 1, 2023

Google ScholarTM

Check