Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams · SIAM Journal on Computing · 2019
We consider the pattern detection problem in graphs: given a constant size pattern graph $H$ and a host graph $G$, determine whether $G$ contains a subgraph isomorphic to $H$. We present the following new improved upper and lower bounds: We prove that if a pattern $H$ contains a $k$-clique subgraph, then detecting whether an $n$ node host graph contains a not necessarily induced copy of $H$ requires at least the time for detecting whether an $n$ node graph contains a $k$-clique. The previous result of this nature required that $H$ contains a $k$-clique which is disjoint from all other $k$-cliques of $H$. We show that if the famous Hadwiger conjecture from graph theory is true, then detecting whether an $n$ node host graph contains a not necessarily induced copy of a pattern with chromatic number $t$ requires at least the time for detecting whether an $n$ node graph contains a $t$-clique. This implies that (1) under Hadwiger's conjecture for every $k$-node pattern $H$, finding an induced copy of $H$ requires at least the time of $\sqrt k$-clique detection and size $\omega(n^{\sqrt{k}/4})$ for any constant depth circuit, and (2) unconditionally, detecting an induced copy of a random $G(k,p)$ pattern with high probability requires at least the time of $\Theta(k/\log k)$-clique detection, and hence also at least size $n^{\Omega(k/\log k)}$ for circuits of constant depth. We show that for every $k$, there exists a $k$-node pattern that contains a $k-1$-clique and that can be detected as an induced subgraph in $n$ node graphs in the best known running time for $k-1$-clique detection. Previously such a result was only known for infinitely many $k$. Finally, we consider the case when the pattern is a directed cycle on $k$ nodes, and we would like to detect whether a directed $m$-edge graph $G$ contains a $k$-cycle as a not necessarily induced subgraph. We resolve a 14- year-old conjecture of [Yuster and Zwick, Proceedings of SODA, 2004, pp. 247--253] on the complexity of $k$-cycle detection by giving a tight analysis of their $k$-cycle algorithm. Our analysis improves the best bounds for $k$-cycle detection in directed graphs for all $k>5$.