Induced Cycles and Paths Are Harder Than You Think

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.