Fine-Grained Classification Of Detecting Dominating Patterns
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911178467311616 |
|---|---|
| author | Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza |
| author_facet | Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fine-Grained Classification Of Detecting Dominating Patterns Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza Data Structures and Algorithms Computational Complexity 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. |
| title | Fine-Grained Classification Of Detecting Dominating Patterns |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2509.22332 |