PACE Solver Description: HitS&DoSeS – Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems

In this paper we provide a short description of the most important algorithms implemented in solver HitS&DoSeS. Due to a large variety of used methods, this description does not contain full information about the algorithms , their details and their behaviour in many distinct situations.

The HitS&DoSeS solver was designed to deal with the generalized dominating set problem (GDS), defined as follows. Given an undirected simple graph $G=(V,E)$ and sets of vertices $H\subseteq V$ and $X\subseteq V$, find the smallest subset $S\subset V\setminus X$ such that, for each node $v\in V\setminus H$, the intersection $N[v]\cap S$ is nonempty.

The solver implemented within HitS&DoSeS for the hitting set problem works by solving the generalized dominating set problem for a bipartite graph $G^{\prime }=(V^{\prime },E^{\prime })$ with bipartition sets $A,B$ and sets $H=A$, $X=B$, where nodes in set $A$ represent elements from universe $U$, nodes in $B$ represent sets from family $F$, and there is an edge $\{a,b\}\in E^{\prime }$ if and only if an element represented by $a$ is contained in the set represented by $b$. This holds for both exact and heuristic solvers for the hitting set problem. Due to this, we will mainly focus on the description of the dominating set solver.

Many combinatorial optimization problems can be treated as an implicit hitting set problem. For example, in the directed feedback vertex set problem the goal is to find a set of vertices that hits all cycles in a given graph. In the GDS, however, the family of sets to hit is given explicitly. This fact may be treated both as an advantage and a disadvantage. On the one hand, the size of the family of sets to hit is clearly bounded (contrary to, e.g., the directed feedback vertex set, where the number of cycles in the graph can be exponential in the graph size). On the other hand, handling only a subset of all constraints can sometimes decrease the size of a problem to tackle and it usually brings some “natural noise” to the computation, which can be beneficial. In the heuristic solver implemented within HitS&DoSeS we simulate generation of sets to hit, as though they were not given explicitly. This enables us to easily add randomization and makes it easier to get out of local optima.

We use an extensive set of data reduction rules for the dominating set problem. This set contains known rules for the dominating set problem ([1]), extensions of those rules, as well as a variety of new reduction rules that were designed, optimized and implemented to be applicable even for very large graph instances. For a given instance of the GDS, the goal is to find one of the following:

1. 1.

   a node that belongs to some optimal solution,

2. 2.

   a node that can be marked as hit (added to set $H$),

3. 3.

   a node that can be marked as excluded (added to set $X$),

4. 4.

   a modification in the graph structure that could make the graph smaller or the structure easier in some sense, usually measured as the size of a result obtained by the local search solver run on the reduced graph.

Designed rules are called exhaustively, until no rule can be applied further or for roughly 25% of total admissible running time, if the preprocessing did not terminate earlier. Many of our rules require lifting a solution after finding it for the reduced graph instance. This is usually due to the fact that it is often possible to conclude that there exists a solution that does not contain a node (the node can be added to $X$) or that a node can be marked as hit and added to $H$, but only if certain additional constraints hold. Many of these constraints are usually fairly difficult to be taken into account when finding a solution using distinct heuristics and approaches, but it is much easier to fix a solution obtained for the reduced instance to make it a valid one for the original instance.

The exact algorithm is conceptually very simple: reduce the graph as much as possible using data reduction rules, then solve the reduced instance using a “general-purpose” solver, applied to the hitting-set formulation of the dominating set problem. In HitS&DoSeS we tested the following algorithms to solve the hitting set problem:

1. 1.

   Integer Linear Programming: HiGHS solver [7] or SCIP solver [4],

2. 2.

   MaxSAT: solving using a MaxSAT approach used by the RC2 solver [8] and either CaDiCaL [3] or Glucose 3 [2] as a SAT solver,

3. 3.

   Constraint Programming: CP-SAT solver [9] from OR-tools software [10].

We also considered a simple branch-and-reduce approach, but our proof-of-concept implementation proved to be much slower than the “general-purpose”-solver approach, hence its further development and optimization were abandoned. By default, the hitting set problem is solved using CP-SAT solver with three workers, as this proved to give the best results (compared to other approaches mentioned above).

The heuristic approach works in a CEGAR (counter-example guided abstraction refinement [6]) fashion. Starting with an empty set $C$ – a subset of a set $𝐂$ containing all neighborhood-constraints (sets of the form $N[v]\setminus X$) generated for the GDS instance, and an initially empty set $S$ (a hitting set of sets in $C$), we iteratively add some subset of unsatisfied constraints (sets in $𝐂$ not hit by $S$), then update $S$ to make it a valid hitting set of sets in $C$.

In order to generate a set of constraints to add to $C$, we select some number of nodes closest to $S$ in the considered graph $G$, nodes farthest from $S$, nodes of smallest/largest degree and several randomly selected nodes; we then add the corresponding constraints. However, the total number of added constraints is limited to at most $\alpha \cdot {|UH|}^{\beta }$, where $UH$ is the set of all nodes $v$ for which the intersection $N[v]\setminus S$ is empty and $\alpha ,\beta$ are parameters whose values depend on basic graph characteristics.

After selecting the set $D$ of constraints to add, we find a hitting set $S_D$ of all sets in $D$ using a local search approach, then create a solution $S^{\prime }$ to $C\cup D$ by taking $S^{\prime }=S\cup S_D$. Next we take $S=S^{\prime }$ and $C=C\cup D$ and try to optimize $S$ using a local search approach. If the size of $S$ could not be improved for a few subsequent iterations, a state perturbation is applied to try to get out of a found local optimum. A state perturbation is achieved by removing some small random subset of nodes in $S$ and/or sets in $C$ (and fixing $S$ afterwards).

Our local search solver for the hitting set problem works by, iteratively, removing a node from $S$ and adding a node back to $S$, unless it is not necessary. A node to remove from $S$ is preferable over other nodes if it has a smaller value of a scoring function $ca(v)$, where $ca(v)$ is equal to the number of sets in $C$ that are hit only by $v$. In case of a tie, a bunch of other heuristics are used. A node to add to $S$ is preferable over other nodes if it has a greater value of a scoring function $hu(v)$, where $hu(v)$ is equal to the number of sets in $C$ that are unhit by $S$ and contain $v$. In case of a tie, a bunch of other heuristics are used, which form variations of rules that can be found in several existing heuristic dominating-set solvers (see, e.g., [11]).

Among the approaches used for tie-breaking, we use the following:

1. 1.

   tabu search to prohibit visiting the same state more than once,

2. 2.

   configuration checking strategy [5],

3. 3.

   selecting the less frequently chosen node if the two compared nodes do not have “similar” state-change frequencies,

4. 4.

   selecting the node that did not change its state for the longest time, if those times the two compared nodes are not “similar”.

To effficiently track changes to values necessary to select next node to add/remove we use a custom-made heap that allows efficient modification of those values without necessity of removing and reinserting the nodes from/to the set. Random node moves are also applied to increase variability. Such random moves usually consist in removing a node and some number of nodes closest to it from the current solution, then adding the same number of nodes back but using the standard comparator to select nodes to add back. Another method of increasing variability used in HitS&DoSeS consists in “freezing” some nodes - prohibiting it from being selected for some number of consecutive iterations.

A variation to the standard add/remove approach is admitted and sometimes executed. This variation allows adding a node to $S$ only if it will result in $S$ being a valid solution. Since we start improvement with a valid solution, such a node always exists, but it might be the same that was just removed from $S$. We observed that this usually cuts the search space, but significantly improves the convergence speed for some instances.

The source code of HitS&DoSeS is freely available and can be found at
https://github.com/swacisko/pace-2025.