2026-07-21T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25164 2026-02-09T08:18:05Z ddc:004 open_access

The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set Grobler, Mario Siebertz, Sebastian PACE 2025 Report Dominating Set Hitting Set Algorithm Engineering FPT Heuristics The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. 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 Mario Grobler and Sebastian Siebertz 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.32 urn:nbn:de:0030-drops-251644 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode