The smallest graph that is not an induced subgraph of a given graph can be found in time \(n^{O(\log n)}\). The exponent is optimal, up to constant factors, under the exponential time hypothesis.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.