PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem

Both dominating set and hitting set instances are solved as unicost set covering instances.

The solving process follows four successive phases:

1. 1.

   Instance reduction

2. 2.

   Initial solution generated by greedy algorithms

3. 3.

   Large neighborhood search

4. 4.

   Local search

The goal of this phase is to reduce the size of the instance to be solved.

The reductions applied are:

• $\mathrm{■}$

  Mandatory sets removal

• $\mathrm{■}$

  Dominated sets removal

• $\mathrm{■}$

  Dominated elements removal

• $\mathrm{■}$

  Set folding

• $\mathrm{■}$

  Unconfined sets reduction

• $\mathrm{■}$

  Small components reduction

The first three reduction rules are classical reductions for set covering problems. They correspond to Reduction 1 to 5 from [4].

The set folding reduction rule corresponds to Reduction 7 from [4] and is a generalization of the vertex folding reduction rule for the vertex cover problem. The idea is to replace a set $j$ that covers two elements, together with its two neighboring sets $j_1$ and $j_2$, by a single set $j^{\prime }$. If $j^{\prime }$ is included in the solution of the reduced problem, then $j_1$ and $j_2$ must be included in the solution of the original problem; otherwise, $j$ must be included in the solution of the original problem.

The unconfined reduction rule is a generalization of the unconfined reduction rule for the vertex cover problem [5]. The idea is to prob the inclusion of a set into an optimal solution and show that another optimal solution without this set exists. If this is the case, then the set can be removed from the instance.

For the small component reduction, we compute simple lower and upper bounds for each connected component of the instance. Any component for which the two bounds coincide can then be removed from the instance.

We also implemented generalizations of the twin reduction rule [5] and the crown reduction rule [3], but they did not have any effect on the challenge instances. Therefore, we did not enable them in our solver.

The large neighborhood search and the local search algorithms require an initial solution. Our initial solution generation procedure relies on 4 greedy algorithms.

• $\mathrm{■}$

  The classical greedy algorithm for the set covering problem: while not all elements are covered, the set covering the highest number of uncovered elements is added to the solution.

• $\mathrm{■}$

  The greedy algorithm from [2]: this greedy algorithm is similar to the classical greedy, but uses a different set scoring function.

• $\mathrm{■}$

  The dual greedy algorithm: in this greedy algorithm, while not all elements are covered, an uncovered element is selected, and a set covering it is added to the solution.

• $\mathrm{■}$

  The reverse greedy algorithm: this greedy algorithm starts with a solution containing all sets. Redundant sets are removed until none remain.

The first two greedy algorithms work well when the number of sets in the solution is small compared to the total number of sets. On the other hand, the reverse greedy algorithm works well when most sets are in the solution.

To determine which greedy algorithm to run, we assess the number of sets in the solution by running the dual greedy algorithm. The dual greedy algorithm is always very fast, although in general it yields worse solutions than the other greedy algorithms.

The goal of this step is to quickly improve the solution obtained in the previous phase.

To this end, we apply a large neighborhood search algorithm. Each element is assigned a weight, initially weight of 1. The score of a set is then defined as the sum of the weights of the uncovered elements it covers.

The large neighborhood search works as follows. At each iteration:

• $\mathrm{■}$

  The set with the worst score is removed from the solution

• $\mathrm{■}$

  The score of the uncovered elements is incremented

• $\mathrm{■}$

  While not all elements are covered, the set with the best score is added to the solution and while the solution contains redundant sets, a redundant set is removed.

The goal of this last phase is to improve the current solution to get the best possible solution.

It implements a local search with a row weighting scheme similar to the one proposed by [2]. If the best feasible solution found so far contains $k$ sets, the local search works on a solution containing $k-1$ sets. As a result, some elements remain uncovered. A weight is associated to each element. The penalty of a solution is defined as the sum of the weights of its uncovered elements. The goal of the local search is to find a solution with penalty $0$. At each iteration, it performs a swap of minimal penalty between a set outside the solution that covers an uncovered element, and one of its set neighbor, that is, a set such that there exists an element that both sets cover. Thus, the solution still contains $k-1$ sets. Then the weight of each newly uncovered element is incremented.

When the number of set neighbors is too high so that computing them makes the solver hit the memory limit, it runs the local search with row weighting from [1] instead. Instead of looking for a swap, at each iteration, this local search first removes a set from the solution, and then adds another one that covers an uncovered element.