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

CREATORJonathan Dransfeld, Marvin Künnemann, Mirza Redzic
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text