A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

arXiv:2404.04369 · cs.DS · Submitted 2024-04-05 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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). p. 0
Where the paper says it

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).

The analysis covers three variants of subgraph isomorphism: Min-Weight Subgraph, Subgraph Listing, and Subgraph Enumeration. p. 9

Where the paper says it

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.

The complexity measure for these three problems is shown to be the same: min to 2. p. 9
Where the paper says it

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.

The main result establishes negative complexity bounds based on specific hypotheses:

  1. 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.

  2. 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.

  3. 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

Where the paper says it

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).

The complexity exponent c(H) is derived from this function F. p. 7
Where the paper says it

We are now ready to state our main result. We start by defining a function that governs the time complexity of simple patterns.

For example:

  • 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

Where the paper says it

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.

A unified approach using H-Encoding treats min-weight, listing, and enumeration problems. p. 9
Where the paper says it

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.

Lower bounds based on clique embeddings demonstrate that the complexity is at least clemb(H), which leads to characterizations of patterns in P. p. 1
Where the paper says it

16 4 Lower Bounds: from General Case to Family P 18 4. 1 Lower Bounds Based on Clique Embeddings .

For instance, Lemma 2. p. 1
Where the paper says it

2 Lower bounds for P(α, β, γ × 2) . 3 Proof of Lemma 2.

8 states: 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

Where the paper says it

, 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.

Similarly, patterns with exponent 2-1/3 arise from stitching together various small graphs. p. 9
Where the paper says it

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.

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

Where the paper says it

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.

The complexity is shown to be the true complexity, conditional on standard hypotheses from fine-grained complexity theory. p. 5
Where the paper says it

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.

The paper also provides detailed analysis of F(alpha, beta, gamma) properties through algebraic lemmas (Lemma 8. p. 1

Where the paper says it

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

14 through 8.19), establishing lower bounds for F in terms of alpha, beta, and gamma. p. 0
Where the paper says it

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.

The final result is that the complexity of H-Encoding for P(alpha, beta, gamma times 2) is O(m 2 - 1/F(alpha, beta, gamma)). p. 2
Where the paper says it

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.

This result is supported by constructions showing that P(9, 2, 2) has complexity 2-1/8 via an encoding algorithm running in time O(m 2 - 1/8). p. 4
Where the paper says it

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).

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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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

Related papers