Search Results

Documents authored by Fink, Simon Dominik


Artifact
Software
The (not-so) Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton


Abstract

Cite as

Alexander Dobler, Simon Dominik Fink, Mathis Rocton. The (not-so) Bad Dominating Set Maker (Software, source code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25245,
   title = {{The (not-so) Bad Dominating Set Maker}}, 
   author = {Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
   note = {Software, Vienna Science and Technology Fund (WWTF) grant [10.47379/ICT19035], Vienna Science and Technology Fund (WWTF) grant [10.47379/ICT22029], European Union’s Horizon 2020 research and innovation COFUND programme (LogiCS@TUWien, grant agreement No 101034440), Austrian Science Fund (FWF) grant [10.55776/Y1329], swhId: \href{https://archive.softwareheritage.org/swh:1:dir:77b0720cd14b92e8d17e114ccf5c1ea89f79dfc9;origin=https://github.com/Doblalex/pace2025;visit=swh:1:snp:db5069228cfc618259ba32a9fe127fd1cb8ef66f;anchor=swh:1:rev:9d5280950b6d22bf75cddbc5bb9d41303b5ba4da}{\texttt{swh:1:dir:77b0720cd14b92e8d17e114ccf5c1ea89f79dfc9}} (visited on 2025-12-15)},
   url = {https://github.com/Doblalex/pace2025},
   doi = {10.4230/artifacts.25245},
}
Document
PACE Solver Description
PACE Solver Description: Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton

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


Abstract
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.

Cite as

Alexander Dobler, Simon Dominik Fink, and Mathis Rocton. PACE Solver Description: Bad Dominating Set Maker. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.IPEC.2025.35,
  author =	{Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
  title =	{{PACE Solver Description: Bad Dominating Set Maker}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{35:1--35:5},
  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.35},
  URN =		{urn:nbn:de:0030-drops-251673},
  doi =		{10.4230/LIPIcs.IPEC.2025.35},
  annote =	{Keywords: Dominating Set, Hitting Set, Pace Challenge}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail