Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles

Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams

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$. Our…