TL;DR
This paper presents the UzL solver for the Dominating Set and Hitting Set problems, which are fundamental NP-hard problems in graph theory. The solver leverages a MaxSAT formulation combined with novel reduction rules and a vertex cover solver for specific cases, achieving competitive performance in the PACE Challenge 2025.
What Problem Does This Paper Address?
The paper tackles two notoriously difficult combinatorial optimization problems: the Dominating Set problem and the Hitting Set problem.
The Dominating Set problem asks for the smallest subset of vertices in a graph such that every vertex in the graph is either in the subset or adjacent to a vertex in the subset. Think of it like finding the minimum number of cell towers to cover an entire region, where towers can cover themselves and their immediate neighbors.
The Hitting Set problem is a generalization that applies to hypergraphs (graphs where edges can connect more than two vertices). The goal is to find the smallest subset of vertices that intersects with every edge (or "hyperedge") in the hypergraph. This is like needing to select a minimum set of people such that every committee (represented by a hyperedge) has at least one selected person.
The paper highlights that the Dominating Set problem can be elegantly transformed into a Hitting Set problem, allowing a unified approach. Both problems are NP-hard, meaning that finding the absolute optimal solution becomes computationally infeasible for large instances. The challenge is to develop algorithms that can find optimal or near-optimal solutions efficiently, especially for the types of instances encountered in competitive challenges like PACE.
Methods
The UzL solver employs a multi-pronged strategy:
- Unified Hitting Set Formulation: The core of the solver treats both Dominating Set and Hitting Set problems as Hitting Set instances. Dominating Set instances are directly translated into their Hitting Set equivalents.
- Presolving with Reduction Rules: Before the main solving phase, the solver applies four novel reduction rules to simplify the hypergraph. These rules are designed to eliminate redundant vertices or edges without affecting the optimality of the solution. Examples include removing vertices that are part of only one edge or simplifying edges that are subsets of others. These rules are shown to subsume some existing reduction rules for Dominating Set.
- MaxSAT Formulation: The Hitting Set problem is then formulated as a MaxSAT (Maximum Satisfiability) problem. This involves defining "hard clauses" that must be satisfied (representing the requirement to hit every edge) and "soft clauses" (representing the objective of minimizing the size of the hitting set). The EvalMaxSAT solver is used to find a solution to this formulation.
- Vertex Cover Solver for Small Instances: For reduced instances that are specifically vertex cover problems (where all hyperedges have size at most 2) and have a limited number of vertices (up to 350), the solver uses a different approach. It leverages a maximum clique solver on the complement graph. The logic here is that the complement of a minimum vertex cover is a maximum independent set, and finding a maximum clique in the complement graph directly relates to finding a minimum vertex cover.
- Lower Bound Computation: The solver attempts to compute a strong lower bound for the hitting set size by looking for a perfect matching in the hypergraph. If a perfect matching is found, it implies a lower bound on the solution size, which is then used in conjunction with a SAT solver (kissat) to verify if this lower bound can be achieved.
Datasets
The paper describes the evaluation of the solver on instances from the PACE Challenge 2025. No new datasets were introduced.
Key Insights and Ideas
- Elegance of Unified Hitting Set: The realization that Dominating Set can be seamlessly converted to Hitting Set simplifies the solver's architecture and allows for a single set of reduction rules to be applied.
- Power of Reduction Rules: The four novel reduction rules are crucial for simplifying complex instances, making them more amenable to the MaxSAT solver. Their effectiveness in reducing instance size is a key contributor to performance.
- Hybrid Approach: Combining a MaxSAT solver with specialized techniques like a vertex cover solver (via maximum clique) and lower bound computations demonstrates a robust strategy for tackling NP-hard problems.
- MaxSAT as a General Tool: The paper reinforces MaxSAT's utility as a powerful general-purpose framework for expressing and solving various combinatorial optimization problems.
Key Results
The paper states that the presolving step, using the reduction rules, executes in fractions of a second and significantly reduces hypergraph sizes. While this leads to faster solving times for many instances, the authors note that on the private test set of the PACE Challenge 2025, the number of instances solvable within 30 minutes did not increase. The vertex cover and matching tricks, while promising, did not trigger on any of the private instances and thus did not affect the competition results.
Limitations and Future Work
- Limited Improvement on Private Test Set: The authors acknowledge that despite the presolving improvements, the overall number of solvable instances within the time limit did not increase on the private test set. This suggests that for harder instances, the MaxSAT solving phase remains the bottleneck.
- Vertex Cover/Matching Tricks Ineffective: The specialized techniques for vertex cover and lower bound computation via matching, while theoretically sound, did not prove beneficial on the specific instances encountered in the competition.
- Parameter Tuning: The paper mentions tweaking internal parameters of EvalMaxSAT, indicating that off-the-shelf solvers might require customization for optimal performance on specific problem classes.
Future work could involve further refining the reduction rules, exploring alternative MaxSAT encodings, or investigating more advanced techniques for the hard instances where the SAT solving dominates computation time. The effectiveness of the vertex cover and matching strategies might also warrant further investigation on different problem distributions.
Summary updated