2026-08-16T16:00:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25167 2026-02-09T08:18:08Z ddc:004 open_access

PACE Solver Description: Bad Dominating Set Maker Dobler, Alexander Fink, Simon Dominik Rocton, Mathis Dominating Set Hitting Set Pace Challenge Dominating Set and Hitting Set are two well-known NP-hard problems on graphs and hypergraphs, respectively. For Dominating Set, we seek a subset S of vertices of minimum size, such that every vertex has a neighbor in S. For Hitting Set, we require that this minimum size subset S intersects each hyperedge. We present Bad Dominating Set Maker, our solver for both problems posed in the exact tracks of the 2025 PACE Challenge. It uses reduction rules, dynamic programming on tree decompositions, and external Vertex Cover and SAT solvers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Dobler and Simon Dominik Fink and Mathis Rocton 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.35 urn:nbn:de:0030-drops-251673 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode