KIT | KIT-Bibliothek | Impressum | Datenschutz

The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set

Großmann, E. ; Heuer, T. ORCID iD icon 1; Schulz, C. ; Strash, D.
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

The Parameterized Algorithms and Computational Experiments challenge (PACE) 2022 was devoted to engineer algorithms solving the NP-hard Directed Feedback Vertex Set (DFVS) problem. The DFVS problem is to find a minimum subset $X ⊆ V$ in a given directed graph $G = (V,E)$ such that, when all vertices of $X$ and their adjacent edges are deleted from $G$, the remainder is acyclic.
Overall, the challenge had 90 participants from 26 teams, 12 countries, and 3 continents that submitted their implementations to this year’s competition. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.


Verlagsausgabe §
DOI: 10.5445/IR/1000154537
Veröffentlicht am 16.01.2023
Originalveröffentlichung
DOI: 10.4230/LIPIcs.IPEC.2022.26
Scopus
Zitationen: 2
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 14.12.2022
Sprache Englisch
Identifikator ISBN: 978-3-9597726-0-0
ISSN: 1868-8969
KITopen-ID: 1000154537
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) , Ed.: H. Dell
Veranstaltung 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Potsdam, Deutschland, 07.09.2022 – 09.09.2022
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 26
Serie Leibniz international proceedings in informatics ; 249
Schlagwörter Feedback Vertex Set, Algorithm Engineering, FPT, Kernelization, Heuristics
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page