2026-07-22T06:31:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17384 2024-03-06T10:59:37Z ddc:004 open_access

PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set Angrick, Sebastian Bals, Ben Casel, Katrin Cohen, Sarel Friedrich, Tobias Hastrich, Niko Hradilak, Theresa Issac, Davis Kißig, Otto Schmidt, Jonas Wendt, Leo directed feedback vertex set vertex cover reduction rules In this document we describe the techniques we used and implemented for our submission to the Parameterized Algorithms and Computational Experiments Challenge (PACE) 2022. The given problem is Directed Feedback Vertex Set (DFVS), where one is given a directed graph G = (V,E) and wants to find a minimum S ⊆ V such that G-S is acyclic. We approach this problem by first exhaustively applying a set of reduction rules. In order to find a minimum DFVS on the remaining instance, we create and solve a series of Vertex Cover instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Angrick and Ben Bals and Katrin Casel and Sarel Cohen and Tobias Friedrich and Niko Hastrich and Theresa Hradilak and Davis Issac and Otto Kißig and Jonas Schmidt and Leo Wendt 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.28 urn:nbn:de:0030-drops-173847 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.28 eng https://creativecommons.org/licenses/by/4.0/legalcode