PACE Solver Description: Weighting-Based Local Search Heuristic for the Hitting Set Problem

Considering that the datasets in the PACE 2025 Challenge may contain millions of sets and elements, applying possible reductions to them is highly beneficial for the subsequent search. We employ three classical reductions without sacrificing optimality [3]:

• $\mathrm{■}$

  Element Dominance: If all sets that cover element $e_i$ also cover element $e_j$ (where $i\ne j$), then $e_j$ can be safely removed.

• $\mathrm{■}$

  Set Dominance: If all elements covered by set $s_i$ are also covered by set $s_j$ (where $i\ne j$), then $s_i$ can be safely removed.

• $\mathrm{■}$

  Mandatory Coverage: If an element $e_i$ is uniquely covered by one set $s_i$, then $s_i$ must be selected, and all elements covered by $s_i$ can be removed.

These reduction rules preserve the existence and structure of optimal solutions. By iteratively applying them, the problem size can typically be reduced significantly. We solve the reduced instance and merge the optimized result with the sets fixed during the reduction process to form the final solution.

We define the importance score $\text{IS}(e_i)=\frac{1}{\text{freq}(e_i)}$ of an element as the reciprocal of its frequency (i.e., the number of sets that can cover it). Then, the score of a set $\text{IS}(s_i)={\sum }_{e_j\in \text{uncovered}(s_i)}\text{IS}(e_j)$ is the sum of the scores of all currently uncovered elements it covers. The greedy algorithm iteratively selects the set with the highest score, thereby prioritizing the coverage of hard-to-cover elements. After each selection, scores of related sets are updated to reflect the new uncovered element set.

Since the number of sets that can cover an element differs from the number of sets that actually cover it in a solution, the original importance score may be biased. To correct this, after obtaining a feasible solution, we refine the score of each element $e_i$ by multiplying it with a scaling factor, i.e., ${\text{IS}}^{\prime }(e_i)=\text{IS}(e_i)\cdot \frac{c_{\text{max}}}{c_i}$, where $c_i$ is the number of times element $e_i$ is actually covered in the solution, and $c_{\text{max}}$ is the maximum coverage count among all elements. Through multiple rounds of score refinement and reconstruction, higher-quality initial solutions can typically be obtained, albeit with increased construction time.

Starting from a feasible initial cover, we iteratively remove a randomly selected set and attempt to reconstruct a feasible cover without increasing the number of sets used. Once such a reconstruction is successful, we obtain an improved solution. Thus, our optimization focuses on how to achieve full coverage using a fixed number of sets.

For instances that contain multiple connected components after reduction, we introduce two dedicated optimization strategies:

• $\mathrm{■}$

  Reducing the number of connected components: We apply a simple branch-and-bound algorithm to exactly solve connected components that involve fewer than $k$ sets (with $k=23$ in our implementation).

• $\mathrm{■}$

  Restricting active components: Initially, the removal of a set introduces uncovered elements in only one connected component. In subsequent swap iterations, if the added set fails to restore full coverage within this component while the removed set belongs to a different component, we revert the current component to its last feasible state.