2026-07-26T16:44:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18360 2024-03-06T11:01:36Z ddc:004 open_access

Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover 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 the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges. 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 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.10 urn:nbn:de:0030-drops-183602 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10 eng https://creativecommons.org/licenses/by/4.0/legalcode