The edit distance function and symmetrization

Ryan Martin

Published 2010-07-12, updated 2012-02-12Version 5

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The distance between a graph, $G$, and a hereditary property, ${\cal H}$, is the minimum of the distance between $G$ and each $G'\in{\cal H}$. The edit distance function of ${\cal 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 ${\cal H}$. This paper develops a method, called 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$. This paper gives some results regarding estimation of the function for an arbitrary hereditary property. This paper also gives the edit distance function for ${\rm Forb}(H)$, where $H$ is a cycle on 9 or fewer vertices.