2026-08-16T22:29:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24567 2025-12-16T14:00:55Z ddc:004 open_access

Fine-Grained Classification of Detecting Dominating Patterns Dransfeld, Jonathan Künnemann, Marvin Redzic, Mirza fine-grained complexity theory domination in graphs subgraph isomorphism classification theorem parameterized algorithms 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 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 all patterns P? Indeed, we define a graph parameter ρ(P) such that if ω = 2, then (n^ρ(P) m^{(|V(P)|-ρ(P))/2})^{1±o(1)} is the optimal running time assuming the Orthogonal Vectors Hypothesis, for all patterns P except the triangle K₃. Here, the host graph G has n vertices and m = Θ(n^α) edges, where 1 ≤ α ≤ 2. The parameter ρ(P) is closely related (but sometimes different) to a parameter δ(P) = max_{S ⊆ 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 dominating) induced P-pattern. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonathan Dransfeld and Marvin Künnemann and Mirza Redzic 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.98 urn:nbn:de:0030-drops-245679 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.98 eng https://creativecommons.org/licenses/by/4.0/legalcode