David Eppstein – Publications

Publications with Virginia Vassilevska Williams

• Quasipolynomiality of the smallest missing induced subgraph.
  D. Eppstein, A. Lincoln, and V. V. Williams.
  arXiv:2306.11185.
  J. Graph Algorithms & Applications 27 (5): 329–339, 2023.

  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.