Quasipolynomiality of the Smallest Missing Induced Subgraph

David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams

We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can b…