Engineering Dominating Patterns: A Fine-grained Case Study

The Dominating H-Pattern problem generalizes the classical k-Dominating Set problem: for a fixed 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 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.