On the query complexity of estimating the distance to hereditary graph properties

Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang +2

Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{F}$-free is estimable with a query complexity t…