On the computation of edit distance functions

Ryan Martin

Published 2010-12-16, updated 2014-09-27Version 3

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The edit distance function of hereditary property, $\mathcal{H}$, is a function of $p\in[0,1]$ and is the limit of the maximum normalized distance between a graph of density $p$ and $\mathcal{H}$. This paper uses localization, for computing the edit distance function of various hereditary properties. For any graph $H$, ${\rm Forb}(H)$ denotes the property of not having an induced copy of $H$. We compute the edit distance function for ${\rm Forb}(H)$, where $H$ is any so-called split graph, and the graph $H_9$, a graph first used to describe the difficulties in computing the edit distance function.