{"ID":2865339,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.22332","arxiv_id":"2509.22332","title":"Fine-Grained Classification Of Detecting Dominating Patterns","abstract":"We consider the following generalization of dominating sets: Let $G$ be a host graph and $P$ be a pattern graph $P$. A dominating $P$-pattern in $G$ is a subset $S$ of vertices in $G$ that (1) forms a dominating set in $G$ \\emph{and} (2) induces a subgraph isomorphic to $P$. The graph theory literature studies the properties of dominating $P$-patterns for various patterns $P$, including cliques, matchings, independent sets, cycles and paths. Previous work (Kunnemann, Redzic 2024) obtains algorithms and conditional lower bounds for detecting dominating $P$-patterns particularly for $P$ being a $k$-clique, a $k$-independent set and a $k$-matching. Their results give conditionally tight lower bounds if $k$ is sufficiently large (where the bound depends the matrix multiplication exponent $ω$). We ask: Can we obtain a classification of the fine-grained complexity for \\emph{all} patterns $P$? Indeed, we define a graph parameter $ρ(P)$ such that if $ω=2$, then \\[ \\left(n^{ρ(P)} m^{\\frac{|V(P)|-ρ(P)}{2}}\\right)^{1\\pm o(1)} \\] is the optimal running time assuming the Orthogonal Vectors Hypothesis, for all patterns $P$ except the triangle $K_3$. Here, the host graph $G$ has $n$ vertices and $m=Θ(n^α)$ edges, where $1\\le α\\le 2$. The parameter $ρ(P)$ is closely related (but sometimes different) to a parameter $δ(P) = \\max_{S\\subseteq V(P)} |S|-|N(S)|$ studied in (Alon 1981) to tightly quantify the maximum number of occurrences of induced subgraphs isomorphic to $P$. Our results stand in contrast to the lack of a full fine-grained classification of detecting an arbitrary (not necessarily \\emph{dominating}) induced $P$-pattern.","short_abstract":"We consider the following generalization of dominating sets: Let $G$ be a host graph and $P$ be a pattern graph $P$. A dominating $P$-pattern in $G$ is a subset $S$ of vertices in $G$ that (1) forms a dominating set in $G$ \\emph{and} (2) induces a subgraph isomorphic to $P$. The graph theory literature studies the prop...","url_abs":"https://arxiv.org/abs/2509.22332","url_pdf":"https://arxiv.org/pdf/2509.22332v1","authors":"[\"Jonathan Dransfeld\",\"Marvin Künnemann\",\"Mirza Redzic\"]","published":"2025-09-26T13:26:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}