A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends".
Jane: Here's the gist of the paper. The paper investigates subgraph isomorphism problems in a colored setting, where nodes of a host graph G are colored by nodes from a pattern graph H.
Tom: The primary objective is to determine all pattern graphs H for which all H-subgraphs can be listed in subquadratic time, specifically in time O(m squared - epsilon + t), where t is the output size.
Jane: For each such subquadratic pattern H, the study characterizes the smallest exponent c(H) such that all H-subgraphs can be listed in time O(mc(H) + t).
Tom: The analysis covers three variants of subgraph isomorphism: Min-Weight Subgraph, Subgraph Listing, and Subgraph Enumeration.
Title and authors: Tom: So we're diving into the paper called "A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends". It looks like this work is trying to figure out exactly which pattern graphs, let's call them H, allow us to find all instances of them in a big graph G faster than quadratic time.
Jane: That sounds really fundamental because subgraph isomorphism is just one of those core problems in computer science, right? So what's the actual goal here with this paper?
Tom: The main point they are making is that they want to determine every pattern H for which we can list all instances in subquadratic time, specifically something like O(m to the power of two minus some small epsilon plus t), where t is just the size of what we find.
Lu: They’re focusing on this colored setting where the nodes in the big graph G are colored by nodes from a fixed pattern graph H, and they are only interested in subgraphs that respect those colors. That adds another layer of constraint to the problem.
Meng: So if we think about what this means for us, it's essentially trying to find a precise map for which patterns are computationally tractable in this constrained environment before we even start looking at specific algorithms.
Lalam: I see how it’s framed as classifying patterns based on their complexity because they’re using a very detailed approach to categorize them.
The paper's summary: Jane: So, summarizing what the authors found in "A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends", they determine which pattern graphs H can have all their instances listed in time better than quadratic, and then they find the smallest exponent, which we call c of H.
Tom: And this exponent is related to some function F that they define based on how they stitch together smaller graphs that are already in P, which is the class of problems solvable in polynomial time.
Lu: They're using this idea where complexity comes from stitching graphs in P along cliques, and the overall complexity exponent c of H comes from the maximum value of a certain function F over all these stitched parts.
Meng: This is interesting because it connects the structure of the pattern H directly to how fast we can solve it, which is a big deal for practical deployment where running time matters on real data.
Lalam: And they’ve shown that for simple shapes like trees, the complexity exponent c of H is just one, meaning they are very efficient.
Jane: But for something more complex like a triangle or a cycle, the complexity gets fractional, which shows how much structure affects the runtime.
The paper's improvements: Tom: They’ve actually identified some specific negative complexity bounds based on certain assumptions they make about other problems in P, which is kind of like proving things false under specific conditions.
Lu: For example, if there exists a pattern H prime that isn't isomorphic to any graph in P, then finding the minimum weight subgraph for H can't be done faster than O(m squared minus some tiny epsilon) if we assume some other hypotheses like the MinClique Hypothesis and MinConv Hypothesis are true.
Meng: That’s useful because it tells us when we can stop looking for a super-fast algorithm for a certain pattern and just stick to what the established complexity bounds say.
Jane: They also show that for listing all instances of H, you can't get better than O(m squared minus some epsilon plus t) if you assume the ZeroClique Hypothesis and the Three Sum Hypothesis are true.
Lalam: And for enumerating all instances, they show that we can't do that in less than O(m squared minus some epsilon plus t) if those same hypotheses hold.
Conclusion: Tom: So to wrap up, the paper "A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends" gives us a way to classify pattern graphs H based on their complexity exponent c of H, which is derived from stitching smaller graphs in P.
Jane: The main implication is that this classification helps us understand the structural properties that determine whether a pattern can be found efficiently, and it provides concrete bounds for when we can expect subquadratic solutions.
Lu: It also gives us a unified way to think about min-weight subgraph finding, listing, and enumeration problems by using this H encoding technique.
Meng: And they’ve shown that the complexity is at least something called clemb of H, which means we have a concrete lower bound based on clique embeddings that rules out certain patterns in P.
Lalam: The paper concludes that all subquadratic complexities are of the form two to the minus one over some integer k, meaning they're all related to powers of two.
Tom: It’s a lot of structural detail, but it really helps us pinpoint exactly what kind of graph structure dictates the efficiency for these fundamental problems.
Jane: It certainly does, and it sets up a direction for future work by showing how to improve algorithms for specific classes like those with smaller exponents.
Karl Bringmann, Egor Gorbachev
Saarland University · Max Planck Institute for Informatics
cs.DS
Submitted: 2024-04-05
Updated: 2026-11-13
Comments: v2: Expanded version establishing a classification of all graphs with subw<2
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: The paper investigates subgraph isomorphism problems in a colored setting, where nodes of a host graph G are colored by nodes from a pattern graph H.
Key concepts
- Subquadratic Complexity
- This refers to an algorithm's running time for finding or listing specific structures within a larger graph that is faster than quadratic time, typically $O(m^2)$. The paper focuses on identifying which pattern graphs H allow these faster solutions.
- Pattern Graph H
- H is the template graph whose subgraphs we are searching for within a host graph G. In this colored setting, the nodes of G are colored by nodes from H, and the goal is to determine if all instances of H can be found efficiently.
- Stitching Graphs in P
- The complexity of a pattern H is determined by how it is constructed by combining simpler graphs from P (a set of tractable problems) using cliques. This construction method defines the exponent $F(\alpha, \beta, \gamma)$ that governs the overall running time complexity.
- Complexity Exponent c(H)
- This value quantifies the inherent difficulty of solving a specific subgraph problem for pattern H. It is derived from the function $F(\alpha, \beta, \gamma)$ related to the graph's construction method. For example, trees have an exponent of 1, while triangles have an exponent of 1.5.
Terminology
Summary
The paper investigates subgraph isomorphism problems in a colored setting, where nodes of a host graph G are colored by nodes from a pattern graph H. p. 2 In
this paper we study the setting where the pattern graph H is fixed and thus of constant
size, while the host graph G is given as the input, and we analyze running time in terms of
the number of edges m of G (and sometimes its number of nodes n). We study the colored
problem variant, where each node of G is colored by a node in H and we ask for a subgraph
respecting these colors. We study the problem of listing all H-subgraphs
in the colored setting, for fixed pattern graphs H. As our main result, we determine all pattern graphs H such that all H-subgraphs can be listed
in subquadratic time O(m2−ε + t), where t is the output size. As our main result, we determine all pattern graphs H such that all H-subgraphs can be listed
in subquadratic time O(m2−ε + t), where t is the output size. Moreover, for each such subquadratic
pattern H we determine the smallest exponent c(H) such that all H-subgraphs can be listed in time
O(mc(H) + t).Where the paper says it
Where the paper says it
Where the paper says it
The analysis covers three variants of subgraph isomorphism: Min-Weight Subgraph, Subgraph Listing, and Subgraph Enumeration. p. 9 Similarly, all
patterns with exponent 2 − 1/3 arise by stitching together any number of K2, K3, C4, C5, C6,
and K3,2 graphs along nodes or edges, in a tree-like fashion, using at least one C5, C6, or
K3,2; etc. 5 Discussion
Our work is a vast generalization of prior results on min-weight, listing, and enumeration
variants of subgraph isomorphism. We show the first results that extend this knowledge beyond the
linear-time regime, characterizing the class of patterns with complexity c for any 1 < c < 2. Our framework is a unified approach to min-weight, listing, and enumeration, which
essentially allows us to rederive prior results in either of these settings for all three settings.Where the paper says it
Where the paper says it
The main result establishes negative complexity bounds based on specific hypotheses:
-
If there exists H' in D(H) such that H' is not isomorphic to any graph in P, then Min-Weight- H-Subgraph cannot be solved in time O(m squared - epsilon) for any epsilon > 0 assuming the MinClique Hypothesis and MinConv Hypothesis.
-
H-Listing cannot be solved in time O(m tilde squared - epsilon + t) for any epsilon > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis. p. 7
Where the paper says it
Let H be a pattern graph. If there exists H′ ∈ D(H) such that H′ is not isomorphic to any graph in P, then Min-Weight-H-Subgraph cannot be solved in time O(m2−ε ) for any ε > 0 assuming the MinClique Hypothesis and MinConv Hypothesis; H-Listing cannot be solved in time Õ(m2−ε + t) for any ε > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis; and H-Enumeration cannot be solved in preprocessing time O(m2−ε ) and delay Õ(1) for any ε > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis.
-
H-Enumeration cannot be solved in preprocessing time O(m squared - epsilon) and delay O(1 tilde) for any epsilon > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis. p. 7
Where the paper says it
Let H be a pattern graph. If there exists H′ ∈ D(H) such that H′ is not isomorphic to any graph in P, then Min-Weight-H-Subgraph cannot be solved in time O(m2−ε ) for any ε > 0 assuming the MinClique Hypothesis and MinConv Hypothesis; H-Listing cannot be solved in time Õ(m2−ε + t) for any ε > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis; and H-Enumeration cannot be solved in preprocessing time O(m2−ε ) and delay Õ(1) for any ε > 0 assuming the ZeroClique Hypothesis and 3SUM Hypothesis.
The complexity of a pattern H is characterized by stitching together graphs in P along cliques, resulting in an overall complexity defined as the maximum of 2-1/F(alpha, beta, gamma) over all stitched parts P(alpha, beta, gamma times 2). p. 8 Actually, stitching along nodes and edges is
sufficient, because no graph in P contains a triangle as a proper subgraph (see Lemma 3. The overall complexity is the maximum of 2−1/F(α, β, γ) over all stitched parts P(α, β, γ×2). We are now ready to state our main result. We start by defining a function that governs
the time complexity of simple patterns.Where the paper says it
Where the paper says it
-
If H is a tree, the complexity is c(H) = 1, as all graphs in D(H) are isomorphic to K 2 = P(1), and F(1, 0, 0) = 1.
-
For the triangle H = K 3, the complexity is c(K 3) = 1.5, as D(H) = H = P(2, 1, 0 times 2), and F(2, 1, 0) = 2. p. 2
Where the paper says it
Alon, Yuster and Zwick found a generalization to k-cycle detection, achieving time O(m2−1/⌈k/2⌉ ) [9]. These running times can be improved using fast matrix multiplication, in particular triangle detection is in time O(m2ω/(ω+1) ) where ω is the exponent of matrix multiplication [9] (see [38] for k-cycles).
-
For a k-cycle H = C k (k at least 4), the complexity is c(C k) = 2-1/ k/2.
The results indicate that all subquadratic complexities are of the form 2-1/k for some integer k in N. p. 8 See Figure 2 for another non-trivial example. One implication of our result is that all subquadratic complexities are of the form 2 − 1/k
for k ∈ N, e. We show the first results that extend this knowledge beyond the
linear-time regime, characterizing the class of patterns with complexity c for any 1 < c < 2. Our framework is a unified approach to min-weight, listing, and enumeration, which
essentially allows us to rederive prior results in either of these settings for all three settings. 16
4 Lower Bounds: from General Case to Family P 18
4. 1 Lower Bounds Based on Clique Embeddings . 2 Lower bounds for P(α, β, γ × 2) . 3 Proof of Lemma 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
For any (alpha, beta, gamma) in P', clemb(P(alpha, beta, gamma times 2)) at least 2-1/F(alpha, beta, gamma).
The paper provides an exhaustive list of patterns in P attaining specific values for F(alpha, beta, gamma), such as those attaining F=2 (e.g., K 3, C 4). All patterns with exponent 2-1/2 arise by stitching together any number of K 2, K 3, and C 4 graphs along nodes or edges in a tree-like fashion, using at least one K 3 or C 4. p. 9 , they arise by
stitching together any number of K2 graphs in a tree-like fashion. Our results show that all
patterns with exponent 2 − 1/2 arise by stitching together any number of K2, K3, and C4
graphs along nodes or edges, in a tree-like fashion, using at least one K3 or C4. Our results show that all
patterns with exponent 2 − 1/2 arise by stitching together any number of K2, K3, and C4
graphs along nodes or edges, in a tree-like fashion, using at least one K3 or C4. Similarly, all
patterns with exponent 2 − 1/3 arise by stitching together any number of K2, K3, C4, C5, C6,
and K3,2 graphs along nodes or edges, in a tree-like fashion, using at least one C5, C6, or
K3,2; etc.Where the paper says it
Where the paper says it
The paper details constructions for lower bounds against specific hypotheses:
-
For P(3, 3, 3), conditional lower bounds based on MinConv Hypothesis or the 3SUM Hypothesis are established by showing that certain verification problems cannot be solved within the claimed time bounds.
-
Detailed constructions show that for various patterns like P(3, 1) and P(3, 1 times), algorithms for Listing and Enumeration can be constructed in time O(m tilde squared - epsilon + t), which contradicts the 3SUM Hypothesis.
The core result is that all subquadratic patterns arise by stitching together graphs in P along nodes and edges in a tree-like fashion. p. 8 8 shows that all subquadratic patterns arise by stitching together
graphs in P along cliques, in a tree-like fashion. Actually, stitching along nodes and edges is
sufficient, because no graph in P contains a triangle as a proper subgraph (see Lemma 3. Super-linear lower bounds for
all non-trees were shown in [42, 22]. Our Results on Subgraph Enumeration
We answer the Subquadratic Enumeration Question, conditional on standard hypotheses
from fine-grained complexity.Where the paper says it
Where the paper says it
The paper also provides detailed analysis of F(alpha, beta, gamma) properties through algebraic lemmas (Lemma 8. p. 1 3 Proof of Lemma 2. 64
8 Algebraic Lemmas 64
A Example: Algorithm and Lower Bound for P (9, 2, 2) 87
B Further Related Work 91
C Computing the Decomposition D(H) 93 This is a vast generalization of the classic results on triangles and cycles. To prove this result, we design new listing algorithms and prove conditional lower bounds based
on standard hypotheses from fine-grained complexity theory. In contrast, from the lower bound perspective, specifically from the perspective of finegrained complexity theory, subgraph detection is a big and completely open problem: Even
for the simple problem of triangle detection conditional lower bounds are elusive; the current
state of the art cannot even rule out linear-time algorithms for triangle detection. 1 Thus, we
cannot hope for determining the optimal running times for a larger class of patterns. 4 A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
with running time Õ(m2ω/(ω+1) + m3(ω−1)/(ω+1)
t
(3−ω)/(ω+1)
) [19]. In a landmark result in
fine-grained complexity, Pˇatraşcu proved that listing t = m triangles in an m-edge graph
cannot be solved in time O(m4/3−ε
) for any ε > 0 assuming the 3SUM hypothesis [68], which
matches the known algorithm [19] if ω = 2 (see also [59, 78] for further developments).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved algorithms for subgraph listing, minimum-weight subgraph finding, and enumeration can be designed for pattern graphs H with subquadratic complexity c(H) < 2 in time O(mc(H) + t), where t is the output size. This applies to all pattern graphs H characterized by stitching together graphs in P along cliques in a tree-like fashion.
-
The system can determine the smallest exponent c(H) for each subquadratic pattern H, providing an optimal complexity measure based on the savings function F(alpha, beta, gamma).
-
The system can utilize clique embeddings to derive conditional lower bounds for subgraph problems based on standard hypotheses like the MinClique Hypothesis and ZeroClique Hypothesis. This allows for ruling out subquadratic algorithms unless these hypotheses fail.
-
The system can solve Minimum-Weight-P(3, 3, 3)-Subgraph in time O(m2 - epsilon) assuming the MinConv Hypothesis or P(3, 3, 3)-Listing in time Otilde(m2 - epsilon + t) assuming the ZeroClique Hypothesis.
-
The system can construct an instance of a host graph G for P(3, 3, 3)-Subgraph by reducing it to the MinConv Verification problem on sequences of length n using a transformation involving nodes defined by A[i] + B[j] - C[k].
Abstract
In an m-edge host graph G, all triangles can be listed in time O(m 1.5) [Itai, Rodeh '78], and all k-cycles can be listed in time O(m 2-1/ k/2 + t) where t is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph G are colored by nodes in the pattern graph H, and we are only interested in subgraphs of G that are isomorphic to the pattern H and respect the colors. We study the problem of listing all H-subgraphs in the colored setting, for fixed pattern graphs H. As our main result, we determine all pattern graphs H such that all H-subgraphs can be listed in subquadratic time O(m 2-epsilon + t), where t is the output size. Moreover, for each such subquadratic pattern H we determine the smallest exponent c(H) such that all H-subgraphs can be listed in time O(m c(H) + t). This is a vast generalization of the classic results on triangles and cycles. We also show the same results for two related problems: finding an H-subgraph of minimum total edge-weight in time O(m c(H)), and enumerating all H-subgraphs in O(m c(H)) preprocessing time and constant delay. Again we determine all pattern graphs H that have complexity c(H) < 2, and for each such subquadratic pattern we determine the optimal complexity c(H). To prove these results, we design new algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. For our algorithms we introduce a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. This technique generalizes the classic high-degree-low-degree approach (which only splits along degrees of single nodes) and is crucial to obtain optimal algorithms.
Sources
- Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
- Simpler Reductions from Exact Triangle
- Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
- Deterministic 3SUM-Hardness
- Listing 6-Cycles
- PANDA: Query Evaluation in Submodular Width
- Leapfrog Triejoin: a worst-case optimal join algorithm
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles