Induced Cycles and Paths Are Harder Than You Think

Mina Dalirrooyfard, Virginia Vassilevska Williams

Introduction

The Subgraph Isomorphism (SI) problem is a cornerstone of graph theory and computational complexity, asking whether a large host graph $G$ contains a copy of a smaller pattern graph $H$. While the general problem is NP-hard, researchers in the field of "fine-grained" complexity seek to understand the exact polynomial-time limits for specific patterns. Recent research from MIT has provided a significant leap in this understanding, specifically regarding induced patterns like paths and cycles. Their work proves that these seemingly simple structures are much harder to detect than previously theorized, establishing new conditional lower bounds that challenge existing algorithmic assumptions.

The Complexity of Induced Patterns

In the induced version of the SI problem, the requirement is strict: the copy of $H$ in $G$ must match $H$ exactly. This means that if two vertices are not connected in the pattern $H$, their corresponding vertices in the host graph $G$ must also lack an edge. This constraint often makes the induced version significantly more difficult than the non-induced version.

While finding a $k$-clique (a fully connected group of $k$ nodes) is recognized as one of the most computationally intensive patterns to locate, the complexity of simpler patterns like paths ($P_k$) and cycles ($C_k$) remained less clear. Prior to this research, the best-known lower bounds suggested that finding an induced $k$-path was at least as hard as finding a $(k/2)$-clique. This paper effectively closes the gap between these lower bounds and the best-known algorithms, suggesting that our current methods are closer to the theoretical limit than we realized.

Methodological Framework

The authors established these new bounds using several sophisticated theoretical techniques:

  • Reductions from $k$-Clique: By using the $k$-Clique hypothesis—the assumption that current clique-finding algorithms are essentially optimal—the researchers established a benchmark to determine the minimum time required for other graph-finding problems.
  • Clique Minors and Graph Cores: The study focuses on "cores" (graphs that cannot be mapped to any proper subgraph via a homomorphism). The authors proved that for any core $H$, the difficulty of detection is tied to the size of its largest clique minor. This structural property is more flexible than a standard clique subgraph, allowing for much stronger hardness proofs.
  • Hyperclique Hypothesis for $C_4$: To address the specific case of the induced 4-cycle ($C_4$), the authors reduced the problem from the 3-Uniform 4-Hyperclique problem, a standard hard problem in computational geometry.
  • Paired Pattern Detection: The researchers introduced a framework where an algorithm must detect either pattern $A$ or pattern $B$. This approach allowed them to demonstrate that certain algorithmic "shortcuts" are mathematically impossible under current hypotheses.

Key Insights and Structural Hardness

The most profound insight of this work is that the hardness of a pattern is fundamentally tied to its structural complexity as defined by its clique minor size, rather than just its largest clique subgraph. This shift in perspective allowed the authors to prove significantly higher hardness for paths and cycles.

Furthermore, the paper sheds light on the "stubbornness" of the induced 4-cycle ($C_4$). As the smallest pattern whose complexity was not well-understood, $C_4$ has long been a point of contention. The authors provide evidence that standard reductions from triangle detection to $C_4$ detection are likely "doomed" to fail, as such a reduction would imply the existence of algorithms that are currently believed to be impossible.

Summary of Results

The research yields several landmark results for fine-grained complexity:

  1. Elevated Hardness for Paths and Cycles: The conditional lower bound for induced $k$-Paths and $k$-Cycles was raised from $(k/2)$-clique hardness to approximately $(3k/4)$-clique hardness. This represents a 50% increase in the exponent of the lower bound.
  2. The $C_4$ Bound: The authors established that $n^{2-o(1)}$ time is necessary to detect an induced $C_4$, even in sparse graphs with only $O(n^{1.5})$ edges. This provides the first conditional lower bound for this elusive pattern.
  3. General Pattern Bounds: The paper proves that for any $k$-node pattern $H$, detecting it is at least as hard as detecting a clique of size $\approx k^{1/4}/1.39$. Notably, this result does not rely on additional mathematical conjectures like the Hadwiger conjecture.

Conclusion and Future Work

While these results significantly narrow the gap between theoretical lower bounds and algorithmic performance, a small margin remains. The best-known algorithms still operate at $k$-clique time, while these new lower bounds sit at $(3k/4)$-clique time. Closing this final gap remains a major open question in the field.

Additionally, while the results for "graph cores" are robust, extending the full strength of the clique-minor analysis to non-core graphs presents a promising future direction. The introduced "Paired Pattern Detection" framework also offers a new tool for researchers to explore whether faster algorithms can be developed for sets of patterns rather than individual ones.

Summary updated

Abstract

The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns H, based on the k-Clique hypothesis that the current best algorithms for Clique are optimal. Our first main result is that for any pattern graph H that is a core, the SI problem for H is at least as hard as t-Clique, where t is the size of the largest clique minor of H. This improves (for cores) the previous known results [Dalirrooyfard-Vassilevska W. STOC’20] that the SI for H is at least as hard as k-clique where k is the size of the largest clique subgraph in H, or the chromatic number of H (under the Hadwiger conjecture). For detecting any graph pattern H, we further remove the dependency of the result of [Dalirrooyfard-Vassilevska W. STOC’20] on the Hadwiger conjecture at the cost of a sub-polynomial decrease in the lower bound. The result for cores allows us to prove that the SI problem for induced k-Path and k-Cycle is harder than previously known. Previously [Floderus et al. Theor. CS 2015] had shown that k-Path and k-Cycle are at least as hard to detect as a $\lfloor$k/2$\rfloor -$Clique. We show that they are in fact at least as hard as 3k/4-O(1)-Clique, improving the conditional lower bound exponent by a factor of 3/2. This shoivs for instance that the knoivn $O(n^{5})$ combinatorial algorithm for 7-cycle detection is conditionally tight. Finally, we provide a new conditional lower bound for detecting induced 4-cycles: $n^{2-o(1)}$ time is necessary even in graphs with n nodes and $O(n^{15})$ edges. The 4-cycle is the smallest induced pattern whose running time is not well-understood. It can be solved in matrix multiplication, $O(n^{\omega})$ time, but no conditional lower bounds were known until ours. We provide evidence that certain types of reductions from triangle detection to 4-Cycle would not be possible. We do this by studying a new problem called Paired Pattern Detection.
BibTeX
@inproceedings{dalirrooyfard2022induced,
  author = {Mina Dalirrooyfard and Virginia Vassilevska Williams},
  title = {{Induced Cycles and Paths Are Harder Than You Think}},
  booktitle = {FOCS},
  year = {2022},
  url = {https://openreview.net/forum?id=_PHOShC-7o1},
}
Figure