Engineering Dominating Patterns: A Fine-grained Case Study
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914091408293888 |
|---|---|
| author | Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza Wunderlich, Marcus |
| author_facet | Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza Wunderlich, Marcus |
| contents | The \emph{Dominating $H$-Pattern} problem generalizes the classical $k$-Dominating Set problem: for a fixed \emph{pattern} $H$ and a given graph $G$, the goal is to find an induced subgraph $S$ of $G$ such that (1) $S$ is isomorphic to $H$, and (2) $S$ forms a dominating set in $G$. Fine-grained complexity results show that on worst-case inputs, any significant improvement over the naive brute-force algorithm is unlikely, as this would refute the Strong Exponential Time Hypothesis. Nevertheless, a recent work by Dransfeld et al. (ESA 2025) reveals some significant improvement potential particularly in \emph{sparse} graphs.
We ask: Can algorithms with conditionally almost-optimal worst-case performance solve the Dominating $H$-Pattern, for selected patterns $H$, efficiently on practical inputs? We develop and experimentally evaluate several approaches on a large benchmark of diverse datasets, including baseline approaches using the Glasgow Subgraph Solver (GSS), the SAT solver Kissat, and the ILP solver Gurobi.
Notably, while a straightforward implementation of the algorithms -- with conditionally close-to-optimal worst-case guarantee -- performs comparably to existing solvers, we propose a tailored Branch-\&-Bound approach -- supplemented with careful pruning techniques -- that achieves improvements of up to two orders of magnitude on our test instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12232 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Engineering Dominating Patterns: A Fine-grained Case Study Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza Wunderlich, Marcus Data Structures and Algorithms The \emph{Dominating $H$-Pattern} problem generalizes the classical $k$-Dominating Set problem: for a fixed \emph{pattern} $H$ and a given graph $G$, the goal is to find an induced subgraph $S$ of $G$ such that (1) $S$ is isomorphic to $H$, and (2) $S$ forms a dominating set in $G$. Fine-grained complexity results show that on worst-case inputs, any significant improvement over the naive brute-force algorithm is unlikely, as this would refute the Strong Exponential Time Hypothesis. Nevertheless, a recent work by Dransfeld et al. (ESA 2025) reveals some significant improvement potential particularly in \emph{sparse} graphs. We ask: Can algorithms with conditionally almost-optimal worst-case performance solve the Dominating $H$-Pattern, for selected patterns $H$, efficiently on practical inputs? We develop and experimentally evaluate several approaches on a large benchmark of diverse datasets, including baseline approaches using the Glasgow Subgraph Solver (GSS), the SAT solver Kissat, and the ILP solver Gurobi. Notably, while a straightforward implementation of the algorithms -- with conditionally close-to-optimal worst-case guarantee -- performs comparably to existing solvers, we propose a tailored Branch-\&-Bound approach -- supplemented with careful pruning techniques -- that achieves improvements of up to two orders of magnitude on our test instances. |
| title | Engineering Dominating Patterns: A Fine-grained Case Study |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.12232 |