Solver for the dominating set problem and hitting set problem, written as an entry to the PACE 2025 challenge. This repository contains code of an exact solver and a heuristic solver.

Requirements:

CMake VERSION 3.15 or higher
c++ 20 or higher
python ortools module with CPSAT solver (use, e.g., ``python3 -m pip install -U --user ortools'')

Please make sure that enough stack space is available (e.g. 8Mb set by default on some linux OS's might be insufficient and likely cause a runtime error).
Solvers were tested after setting the limit using ``ulimit -s 1000000'' command.

Installation:

Use cmake to obtain a binary file, e.g. in linux in the main directory (pace-2025) you can use the following commands:

mkdir build
cp solveCPSAT.py build/solveCPSAT.py
cd build
cmake ..
make

After this, the executable files should be in the "build" directory.

Usage:

./solver_executable < example_input.gr > example_output.out

Heuristic solvers will be run by default for 290 seconds (possibly with some slight overhead for very large instances, needed to terminate computation and print result).