The (not-so) Bad Dominating Set Maker

This Bad Dominating Set Maker is an exact solver for the 2025 PACE challenge on Dominating Set and, through its Hitting Set Upgrade, also for Hitting Set. This project can be directly built with CMake to obtain the main binary ogdf_dsexact (which can also solve Hitting Set instances) and also the companion ogdf_validate that allows validating solutions generated by the former:

git clone https://github.com/Doblalex/pace2025.git
cd pace2025
git submodule update --init --recursive

mkdir build-release && pushd build-release
cmake .. # by default we have CMAKE_BUILD_TYPE=Release
make -j $(nproc)
popd

inst=instances/small/bremen_subgraph_20.gr
cat $inst | build-release/ogdf_dsexact | tee out.txt
cat out.txt | build-release/ogdf_validate $inst

Alternatively, see the Dockerfile for a containerized build:

docker build . -t pace25-bdsm
cat instances/small/bremen_subgraph_20.gr | docker run -i pace25-bdsm ogdf_dsexact

In its default configuration, the project depends on (slightly modified versions of) the OGDF, htd, peaty, and EvalMaxSAT. All these dependencies are registered as git submodules in the ./ext folder and will be built in an appropriate configuration by the main CMakeFile. See the commented-out or-tools module in .gitmodules and ext/build-uwrmaxsat.sh for the other, alternative MaxSAT solvers that can be used instead of EvalMaxSAT.

Peaty is called as external executable that needs to be located at the path ./ext/peaty/solve_vc relative to the path of the ogdf_dsexact executable. Our CMake build ensures that peaty is built and available at that path, but you also need to move solve_vs accordingly when moving the ogdf_dsexact executable. Additionally, the coreutils /usr/bin/timeout executable needs to be available to wrap the call to peaty.

CMake Options

Option	Default	Description
PACE_USE_GUROBI, PACE_USE_EVALMAXSAT, PACE_USE_UWRMAXSAT, PACE_USE_ORTOOLS	PACE_USE_EVALMAXSAT=ON, others OFF	select which MaxSAT solver to use, exactly one option needs to be ON
PACE_SAT_CACHE	OFF	whether to cache MaxSAT solution on the file system
PACE_LOG	OFF	whether to enable debug logging
PACE_ARCH,OGDF_ARCH	native	target architecture of the binary, use haswell for optil static binaries
PACE_USE_ASAN	OFF	whether to enable the Google AddressSanitzer
CMAKE_BUILD_TYPE	Release	the usual CMake Release or Debug build switch
CMAKE_INTERPROCEDURAL_OPTIMIZATION	ON for Release, otherwise OFF	whether to perform further optimization of the whole static binary
BUILD_SHARED_LIBS	OFF for Release, otherwise ON	whether to statically or dynamically link dependencies