One of the most basic questions about detecting patterns in data is the Induced Subgraph Detection problem. Here we are given a small pattern graph and a large host graph, and are tasked with determining if the host contains
the pattern as an induced subgraph. One of the dream goals of fine-grained complexity and graph algorithms is to fully classify those patterns for which Induced Subgraph Detection is easy to solve, and those for which it becomes difficult. In this talk, we
present some recent, surprising progress on this classification question, centered around a particularly suspicious pattern known as the 4-cycle.
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}