Induced Cycles and Paths Are Harder Than You Think

Download PDF

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 {\em 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 {\em subgraph} in H, or the chromatic number of H (under the Hadwiger conjecture). For detecting \emph{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.
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^{1.5}) edges.