This repository contains the code accompanying my bachelor's thesis. For my submission to the PACE Challenge 2025 - Dominating Set Heuristic Track, see this repository.
Install Make and GCC if not already present. Then simply run
make releaseThis will produce a binary executable which can be found at build/release/heuristic_solver.
For anyone interested in understanding or working on the source code: run make help for a list of additional targets.
- The C standard library
- The C POSIX library
The executable will read an input graph from stdin. It will then try to solve it as well as possible until it receives a SIGTERM signal, after which it will output its solution to stdout. Note that it may stop delayed or may not stop at all if it receives the SIGTERM signal within the first 20 seconds of execution (or longer if the input graph is too dense).
For a more detailed explanation, see Thesis.pdf.
After an initial reduction phase, the greedy vote algorithm is used to obtain an initial solution. The remaining time is then spent on the iterated greedy algorithm, which, at each iteration step, partially deconstructs the current solution (making it an invalid solution, leaving some vertices undominated) and then reconstructs it to a new valid solution. If the solution found this way is as good as or better than the current best solution, it is adopted and saved as the new best solution. Otherwise, the new solution is discarded and the current best solution is restored.
The aim of our reduction phase is both to reduce the size of the graph (resulting in a speed-up for the subsequent iterated greedy algorithm) and identify vertices that are optimal choices to pick for a dominating set.
The reduction is based on J. Alber, M. R. Fellows, R. Niedermeier. Polynomial Time Data Reduction for Dominating Set, arXiv:cs/0207066v1. We use the same slight modifications to the reduction rules as described in Section 4 of the paper, i.e., instead of attaching gadget vertices, we remove vertices that are found to be optimal choices and mark their neighbors as dominated.
We use the some additional modifications to the reduction rules not described by Alber et al.:
- Neighbors of v that are already marked dominated may be in either N1(v) or N2(v), but never in N3(v). Likewise for N(v, w).
- For rule 1, we not only reduce if N3(v) is non-empty, but also if both v is not marked dominated and N1(v) is empty.
- For rule 2, we use additional rules to reduce components consisting of just the neighborhood N[v, w].
Similar to the implementation described in the paper, we also identify and reduce vertices previously marked dominated that have become redundant, i.e., their removal does not change the set of all possible dominating sets of a graph. However, whereas Alber et al. only use three simple rules for dominated vertices of degree 0 or 1, 2, and 3, we use a generalized rule: any vertex v marked dominated is removed if all of its undominated neighbors share at least one other common neighbor besides v.
This reduction phase ends if either the graph cannot be reduced any further using these reduction rules, or if the time budget for the reduction runs out.
We use a time budget of 7.5 seconds to check all reduction rules including rule 2, followed by 5.5 more seconds in which only rule 1 and the redundancy rule are checked.
Similar to the standard greedy algorithm for the dominating set problem, in each iteration step, the greedy vote algorithm takes the vertex ranking highest in a metric and adds it to the solution set. It repeats this until the solution set has become a dominating set. The standard greedy algorithm and the greedy vote algorithm differ only in the metrics they use to rank candidate vertices. Whereas the standard greedy algorithm ranks vertices by their number of currently undominated neighbors, greedy vote uses a slightly more complicated metric: Each currently undominated vertex has a voting power of 1, which it divides equally among all vertices it could be dominated by, i.e., its neighbors and itself. This means it gives 1/(degree + 1) votes to each neighbor and to itself. The sum of all votes received by a vertex is called its weight. Greedy vote uses this weight as its metric, picking the vertex with the greatest weight in each iteration step.
More information on the greedy vote algorithm can be found in Sanchis, L. Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. Algorithmica 33, 3–18 (2002).
Greedy vote sometimes picks vertices that are later rendered redundant by vertices picked in steps further down the line. A vertex v is redundant in a dominating set S if and only if S without v is still a dominating set. To obtain a minimal dominating set (i.e. local minimum), we iterate over all vertices in the dominating set found by the greedy vote algorithm and drop those vertices v, for which v itself and any neighbor of v are each dominated by at least two vertices. We always run this minimization after a new solution is calculated using the greedy vote algorithm.
Our solver uses two distinct strategies to partially deconstruct a current solution:
Each vertex in the current solution is dropped with a probability of 1.2%.
Starting from a randomly selected vertex of the graph, we run breadth-first search and drop any visited vertex from the solution if it is in it. We stop as soon as 40 vertices have been dropped from the current solution or if the breadth-first search terminates (which can only happen if all vertices of a component have been visited).
In each deconstruct-reconstruct-cycle of the iterated greedy algorithm, the deconstruction strategy is selected randomly, favoring the strategy that had a higher success rate in the recent past. To do that, each strategy is assigned a score. Each time we use a deconstruction strategy, its score is multiplied by the decay factor 0.9. If the subsequent reconstruction results in a better solution, a reward of 1.0 is added to the score of the deconstruction strategy used. No reward is added if the reconstruction results in an equally good or worse solution.
The probability for selecting each strategy is proportional to its current score, but clamped between the minimal probability of 0.2 and the maximal probability of 0.8.