Quasipolynomiality of the Smallest Missing Induced Subgraph
Vol. 27, no. 5, pp. 329-339, 2023. Regular paper.
Abstract 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 be found by a brute-force search, in an $n$-vertex graph, in time $n^{O(\log n)}$. We show that under the Exponential Time Hypothesis this quasipolynomial time bound is optimal. We also consider variations of the problem in which either the missing subgraph or the given graph comes from a restricted graph family; for instance, we prove that the smallest missing planar induced subgraph of a given planar graph can be found in polynomial time.

 This work is licensed under the terms of the CC-BY license.
Submitted: September 2022.
Reviewed: February 2023.
Revised: June 2023.
Accepted: June 2023.
Final: June 2023.
Published: July 2023.
Communicated by Anna Lubiw
article (PDF)