DROPS

Document

PACE Solver Description

DOI: 10.4230/LIPIcs.IPEC.2025.36

PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem

Authors: Florian Fontan and Guillaume Verger

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract

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.

Cite as

Florian Fontan and Guillaume Verger. PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 36:1-36:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fontan_et_al:LIPIcs.IPEC.2025.36,
  author =	{Fontan, Florian and Verger, Guillaume},
  title =	{{PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{36:1--36:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.36},
  URN =		{urn:nbn:de:0030-drops-251681},
  doi =		{10.4230/LIPIcs.IPEC.2025.36},
  annote =	{Keywords: dominating set, hitting set, unicost set covering, reductions, large neighborhood search, local search}
}

Search Results

Documents authored by Verger, Guillaume

PACE Solver Description: Reductions and Heuristic Search for the Dominating Set Problem and the Hitting Set Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message