Fine-Grained Classification Of Detecting Dominating Patterns
Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic · 2025
Read Fine-Grained Classification Of Detecting Dominating Patterns by Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22332.txt.
Introduction
Jonathan Dransfeld, Marvin Künnemann, and Mirza Redzic classify the exact difficulty of a family of graph pattern problems in this 2025 paper. The problems concern dominating patterns: a set of vertices that both dominates the graph, touching every vertex, and forms a specified pattern shape, such as a clique, a matching, or a path. Graph theorists had studied such patterns case by case. Prior work gave algorithms and lower bounds for a few patterns, tight only when the pattern is large.
The authors ask for a complete classification covering every pattern at once. They define a parameter of the pattern that determines the optimal running time, assuming a standard hypothesis from fine-grained complexity. One pattern, the triangle, is the lone exception. The classification leans on a quantity studied since the nineteen eighties for counting pattern occurrences, though the two sometimes differ.
Catalog record
| CREATOR | Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22332
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fine-Grained Classification Of Detecting Dominating Patterns Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic Abstract We consider the following generalization of dominating sets: Let G G be a host graph and P P be a pattern graph P P . A dominating P P -pattern in G G is a subset S S of vertices in G G that (1) forms a dominating set in G G and (2) induces a subgraph isomorphic to P P . The graph theory literature studies the properties of dominating P P -patterns for various patterns P P , including cliques, matchings, independent sets, cycles and paths. Previous work (Kunnemann, Redzic 2024) obtains algorithms and conditional lower bounds for detecting dominating P P -patterns particularly for P P being a k k -clique, a k k -independent set and a k k -matching. Their results give conditionally tight lower bounds if k k is sufficiently large (where the bound depends the matrix multiplication exponent ω \omega ). We ask: Can we obtain a classification of the fine-grained complexity for all patterns P P ? Indeed, we define a graph parameter ρ ( P ) \rho(P) such that if ω = 2 \omega=2 , then ( n ρ ( P ) m | V ( P ) | − ρ ( P ) 2 ) 1 ± o ( 1 ) \left(n^{\rho(P)}m^{\frac{|V(P)|-\rho(P)}{2}}\right)^{1\pm o(1)} is the optimal running time assuming the Orthogonal Vectors Hypothesis, for all patterns P P except the triangle K 3 K_{3} . Here, the host graph G G has n n vertices and m = Θ ( n α ) m=\Theta(n^{\alpha}) edges, where 1 ≤ α ≤ 2 1\leq\alpha\leq 2 . The parameter ρ ( P ) \rho(P) is closely related (but sometimes different) to a parameter δ ( P ) = max S ⊆ V ( P ) | S | − | N ( S ) | \delta(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 P . Our results stand in contrast to the lack of a full fine-grained classification of detecting an arbitrary (not necessarily dominating ) induced P P -pattern. Karlsruhe Institute of [email protected] Karlsruhe Institute of [email protected]://orcid.org/0000-0003-4813-4852 Karlsruhe Institute of [email protected]://orcid.org/0009-0001-7509-1686 ccs Theory of computation Graph algorithms analysis ccs Theory of computation Parameterized complexity and exact algorithms ccs Theory of computation Problems, reductions and completeness keywords fine-grained complexity theory, domination in graphs, subgraph isomorphism, classification theorem, parameterized algorithms † † copyright: † † runningauthor: J. Dransfeld, M.Künnemann, M. Redzic † † funding: Research supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 462679611. † † editors: Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman † † event-title: 33rd Annual European Symposium on Algorithms (ESA 2025) † † event-shorttitle: ESA 2025 † † event-acronym: ESA † † year: 2025 † † event-date: September 15–17, 2025 † † event-location: Warsaw, Poland † † series-volume: 351 † † articleno: 97 1 Introduction Among the most intensively investigated graph problems is the dominating set problem: Given a graph G=(V,E) , find a (small) vertex subset S\subseteq V that dominates all vertices, i.e., for each v\in V , we have v\in S or there is some s\in S with \{s,v\}\in E . In many scenarios, one might not merely want to find any dominating set, but rather a dominating set S satisfying some additional requirements. Possibilities include S forming a connected subgraph, admitting a perfect matching, or more generally being connected by a prescribed topology (e.g., rings or cliques) or even being fully disconnected (i.e., forming an independent set). In this work, we study a general form of such problems: For any pattern graph H , the (Non-induced) Dominating P -Pattern problem asks to determine, given a graph G , whether there exists a (non-)induced copy of P in G that dominates all vertices of G . Indeed, for various patterns P , the structural properties of Dominating P -Patterns have been well investigated, e.g., Dominating Cliques [ 6 , 13 , 18 , 21 , 33 , 34 , 35 ] , Dominating Independent Sets 1 1 1 We remark that a Dominating Independent Set is equivalent to the well-studied notion of a Maximal Independent Set. [ 14 , 15 , 16 , 36 , 44 ] , Dominating (Induced) Matchings [ 29 , 48 , 49 ] , Dominating Cycles [ 23 , 24 ] or Dominating Paths [ 25 , 26 , 54 ] . Recently, the algorithmic complexity of detecting Dominating P -Patterns in general graphs has been performed by Künnemann and Redzic, focusing on cliques, independent sets and perfect matchings [ 37 ] (see below for further details). In this work, we set out to understand the fine-grained complexity of this problem for all patterns P . Note that the Dominating P -Pattern problem is the natural combination of two classic problems which are heavily studied in isolation: Dominating Set and P -Pattern Detection. • k -Dominating Set : Dominating set is a notoriously difficult problem. When parameterized by the solution size k (i.e., |S|) , it is the arguably most natural W[2]-complete problem and hard even to approximate within f(k) factors [ 10 , 31 ] . The best known algorithm is based on fast matrix multiplication and solves it in time n^{k+o(1)} for all sufficiently large k [ 22 ] . This is tight in the sense that an \mathcal{O}(n^{k-\epsilon}) -time algorithm for any k\geq 3 and \epsilon>0 would refute the k -Orthogonal Vectors Hypothesis ( k -OVH) and thus the Strong Exponential Time Hypothesis [ 46 ] (see Section 2 for details). Taking the graph sparsity (i.e., the number m of edges) into account as well, a recent result [ 27 ] gives upper and conditional lower bounds establishing a tight time complexity of mn^{k-2\pm o(1)} if the matrix multiplication exponent \omega is equal to 2 . • P -Pattern Detection (aka Induced P -Subgraph Isomorphism): The complexity of P -Pattern Detection for general P is sensitive to the considered pattern P . The probably most notable special case is k -Clique Detection. It is the most natural W[1] -complete problem and also resists good approximations [ 10 , 38 , 30 ] . Its best known algorithm solves it in time essentially \mathcal{O}(n^{\frac{\omega}{3}k}) [ 42 ] 2 2 2 If k is divisible by 3. and is conjectured to be optimal, see, e.g., [ 1 ] . For other (classes of) patterns P , however, only partial results are known: While for any k -node pattern P , the problem can be reduced to k -Clique Detection, this approach is not necessarily optimal. E.g., all 4-node patterns except clique and independent set can be detected polynomially faster than the conjectured time for clique and independent set, see in particular [ 32 , 22 , 51 , 19 ] . Despite significant effort (see [ 32 , 22 , 51 , 20 , 19 ] for a selection), the task of finding matching upper and conditional lower bounds appears far from completed. Let us remark that also for Non-induced P