2026-07-24T05:47:31Z https://drops.dagstuhl.de/oai

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

The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set Großmann, Ernestine Heuer, Tobias Schulz, Christian Strash, Darren Feedback Vertex Set Algorithm Engineering FPT Kernelization Heuristics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ernestine Großmann and Tobias Heuer and Christian Schulz and Darren Strash 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.26 urn:nbn:de:0030-drops-173826 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.26 eng https://creativecommons.org/licenses/by/4.0/legalcode