Exact algorithm for dominating set: the PACE challenge 2025

Abstract

This thesis presents an exact adaptive algorithm for the minimum dominating set problem (MDS), developed as a submission for the exact track of the PACE 2025 challenge. The algorithm leverages key structural properties of input graphs such as treewidth, connectivity, and vertex count. At the core of our algorithm lies a novel generali sation of the minimum dominating set problem, called the aug mented minimum dominating set problem (AMDS). This new formulation allows us to unify and extend existing reduction rules while preserving the essential structural information needed to ef fectively solve the minimum dominating set problem. To solve instances of the AMDS problem, two complementary approaches are implemented, both tailored to leverage the additional contextual infor mation provided by the AMDS formulation. A dynamic programming algorithm bounded by treewidth is used for graphs with low treewidth, whereas ILP and CP-SAT formulations are introduced to handle in stances of higher treewidth. An extensive experimental evaluation on the PACE 2025 dataset is conducted to support and justify the design choices made.