2026-07-24T11:33:22Z https://drops.dagstuhl.de/oai

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

PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem Fontan, Florian Verger, Guillaume dominating set hitting set unicost set covering reductions large neighborhood search local search In this paper, we describe the solver we submitted for both heuristic tracks of the PACE challenge 2025 on the dominating set problem and the hitting set problem. We solve both problems as unicost set covering problems. Our solver first performs reductions on the instance. Then greedy algorithms generate an initial solution that serves as starting point of the large neighborhood search and the local search which are executed afterwards. The solver ranked first in the dominating set heuristic track, and second in the hitting set heuristic track. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Fontan and Guillaume Verger 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.36 urn:nbn:de:0030-drops-251681 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode