{"ID":2855600,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12232","arxiv_id":"2510.12232","title":"Engineering Dominating Patterns: A Fine-grained Case Study","abstract":"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-\\\u0026-Bound approach -- supplemented with careful pruning techniques -- that achieves improvements of up to two orders of magnitude on our test instances.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.12232","url_pdf":"https://arxiv.org/pdf/2510.12232v1","authors":"[\"Jonathan Dransfeld\",\"Marvin Künnemann\",\"Mirza Redzic\",\"Marcus Wunderlich\"]","published":"2025-10-14T07:35:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}