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.SEA.2023.10
URN: urn:nbn:de:0030-drops-183602
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18360/
Angrick, Sebastian ;
Bals, Ben ;
Casel, Katrin ;
Cohen, Sarel ;
Friedrich, Tobias ;
Hastrich, Niko ;
Hradilak, Theresa ;
Issac, Davis ;
Kißig, Otto ;
Schmidt, Jonas ;
Wendt, Leo
Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover
Abstract
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.
BibTeX - Entry
@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10,
author = {Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
title = {{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {10:1--10:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18360},
URN = {urn:nbn:de:0030-drops-183602},
doi = {10.4230/LIPIcs.SEA.2023.10},
annote = {Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
