The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Each exact track of PACE 2025 consisted of 200 benchmark instances, split into 100 public and 100 private instances. While the public instances were released for solver development and testing, the official evaluation was performed solely on the private set. Each solver was given a time limit of 30 minutes per instance, with an additional mercy time of 25 seconds, and was executed under a memory cap of 16 GB RAM, increased from 8 GB in previous years. To ensure reliability, an additional verification phase was conducted to verify correctness of submitted solvers. As in earlier editions, only solvers implementing provably correct algorithms were permitted, although formal proofs of correctness were not required. The winner of each track was determined by the number of solved private instances; in case of ties, the cumulative running time served as the tie-breaker.

The heuristic tracks of PACE 2025 followed a setup similar to the exact tracks, with 200 benchmark instances in total, split into 100 public and 100 private instances. Each solver was given a time limit of 5 minutes per instance, after which a SIGTERM signal was sent, followed by an additional 20 seconds mercy time before a final SIGKILL was sent. The mercy time was primarily intended to ensure that solvers had a sufficient amount of time to write their output after termination was requested. As in the exact tracks, each solver was executed under a memory cap of 16 GB RAM, increased from 8 GB in previous years. Submissions were ranked by the sum over all instances of the scores computed by the function $f(k)={\left(\frac{u-k}{u-k^{\ast }}\right)}^2$, where $u=\min \{n,2k^{\ast }\}$, $k^{\ast }$ is the best known solution value for the instance and $k$ is the produced solution value. Hence, improving already good solutions was more beneficial than improving bad solutions, and instances where $k^{\ast }$ is much smaller than $n$ did not automatically yield a score of close-to-one.

The benchmark set of PACE 2025 was selected with the objective of providing instances with nice structural properties, rather than relying solely on random or synthetic constructions. The collection was drawn from a diverse set of sources:

• $\mathrm{■}$

  OpenStreetMap (OSM). These instances are (nearly) planar graphs derived from road networks. Interestingly, many solvers were able to compute exact solutions very efficiently on such instances, even for comparatively large graphs.

• $\mathrm{■}$

  SATLIB. Graph instances obtained from reductions of SATLIB benchmarks [21], which inherit structural features of the underlying SAT formulas. Again, a large fraction of solvers was capable of producing exact solutions within short running times

• $\mathrm{■}$

  Watts-Strogatz random graphs. The Watts-Strogatz model generates graphs by starting from a regular ring lattice and randomly rewiring edges with a given probability, thereby interpolating between regular and small-world structures. In contrast to the previous categories, these instances proved particularly challenging: even relatively small graphs remained intractable for most solvers.

• $\mathrm{■}$

  Previous PACE challenges. A small subset of instances was reused from earlier editions, in particular from PACE 2019 (Vertex Cover) and PACE 2021 (Cluster Editing).

• $\mathrm{■}$

  Other. The remaining instances include e.g. social network graphs derived from real-world social networks, such as Facebook. Despite their large size, many of these graphs could be solved quickly, with optimal solution sizes typically being very small. Other instances orginate from action sequences or were obtained by taking disjoint unions of the aforementioned instances with additional random edges between the components.

The benchmark set was employed uniformly across both Dominating Set and Hitting Set, and across both exact and heuristic tracks. For the heuristic tracks, larger instances were selected. Where necessary, appropriate reductions were applied to adapt instances to the respective problem formulations. For example, SAT instances were reduced to Dominating Set or Hitting Set, either directly or via intermediate reductions such as Vertex Cover. This ensured that structurally rich instances could be shared across problems and tracks. We note that the public benchmark set did not include any Watts-Strogatz instances. All other categories were approximately balanced between public and private sets. As the other categories turned out to be quite easy for many solvers, there was a high chance that many teams would achieve perfect scores on the public instances. As Watts-Strogatz graphs turned out to be considerably more difficult, they were eventually incorporated into the private test set. Importantly, in the exact tracks of both Dominating Set and Hitting Set, every non-Watts-Strogatz instance was solved by at least one solver. The only unsolved cases were precisely the Watts-Strogatz instances: 14 in the Dominating Set track and 15 in the Hitting Set track, underlining their role as the most challenging instances.

For the first time in the history of the PACE challenge, a dedicated verification phase was introduced. In this phase, all submitted solvers were made publicly available to the community, and participants were explicitly invited to test each other’s implementations in order to identify possible bugs. Moreover, all solvers were evaluated against a large verification dataset, which was not used for scoring but served as an additional safeguard: solvers that produced incorrect solutions on any of these instances were allowed to be repaired in case of minor fixes and otherwise disqualified from the competition.

The verification set included large numbers of random graphs generated under different generative models, such as the Erdős-Rényi model [16], the Barabási-Albert model [5], the Watts-Strogatz model [33], and power-law cluster graphs following the algorithm of Holme and Kim [20], as well as uniform intersection graphs and several additional random graph models. In addition, the dataset contained named graphs such as grids, trees, ladders, cliques, paths, and wheels. Finally, a randomly selected subset of the large-scale STRIDE dataset (Sharing and Testing Repository for Instance Deployment and Evaluation, available at https://domset.algorithm.engineering/), which is maintained by Manuel Penschuck.

For baseline testing, the organizers employed an internal solver combining a set of problem-specific reduction rules with the commercial ILP solver CPLEX [10]. For both problems, dedicated verifiers were made available to participants; these were implemented as Java/Maven projects and ensured the correctness of submitted solutions (however, optimality was not checked). All solvers were executed inside Docker containers, using a common template that was also released publicly. Each container provided an identical environment, based on Ubuntu with 16 GB RAM and a single CPU core, thereby guaranteeing portability and reproducibility. This homogeneous setup allowed all solvers to be executed seamlessly on the compute cluster of the Data Science Center at the University of Bremen (https://www.dsc-ub.de/), ensuring fair and consistent evaluation across teams.

Organizing the 10th iteration of the PACE Challenge has also provided valuable insights. It turned out to be highly challenging to design a benchmark set that is both structurally rich and well balanced in difficulty; while some classes of instances were solved quickly by nearly all solvers, others (notably the Watts–Strogatz graphs) proved unexpectedly difficult. Closely related, although creating a timeline for the organization is straightforward, adhering to it in practice turned out to be considerably harder. The discrepancy between the public and private instance sets, again caused by the delayed inclusion of Watts–Strogatz graphs, understandably led to surprise and discussion among participants.

On the technical side, the process of setting up Docker containers for all solvers was very time-consuming, but the effort clearly paid off: it ensured portability, reproducibility, and a fair evaluation across the homogeneous infrastructure provided by the Data Science Center at the University of Bremen. Finally, the verification phase to ensure correctness of solvers proved to be extremely valuable. It revealed a range of issues, including small implementation bugs such as failure to handle comment lines in input files, conceptual oversights such as missing coverage of corner cases, and configuration problems such as insufficient numerical precision of external ILP solvers. Thanks to this process, nearly all issues could be resolved before the official evaluation, and in the end only two solvers had to be disqualified for producing incorrect or suboptimal solutions in the exact track. We thank Manuel Penschuck for preparing the STRIDE repository and for his valuable remarks in catching the aforementioned bugs!

Despite their difficulty, the Watts–Strogatz instances also provided particularly valuable insights. In total, 14 instances in Dominating Set and 15 instances in Hitting Set could not be solved by any solver. At the same time, the best-performing solvers solved only 81 instances (DS) and 79 instances (HS), respectively. This implies that even the strongest solvers failed on at least five, resp. six, instances that some other solver was able to handle successfully. Thus, no single solver dominated across the entire instance set, and the comparison revealed genuine diversity in algorithmic strengths.

This observation opens a promising avenue for future research. Since different solvers excelled on different subsets of the benchmark, it becomes natural to ask whether the underlying algorithmic ideas and engineering concepts can be combined. A solver that unifies the complementary strengths of existing methods might be capable of solving all instances that were solved by at least one team.

The experiences from PACE 2025 reinforce the importance of combining strong theoretical foundations with robust engineering practices. Future iterations of the PACE Challenge will continue to build on these lessons, refining the evaluation methodology, strengthening the benchmarking process, and fostering collaboration across different areas of algorithm design. We are looking forward to PACE 2026!