A generalization of the most common subgraph distance and its application to graph editing

We relate the graph editing distance to a generalized weighted version of the most common subgraph distance. To do so, we introduce the new concepts of isotonic shifts and vector weighted graphs. As a consequence we can give a weak but sufficient condition on cost models to result in an edit metric, ensuring the richness of the class of these functions. Moreover, for arbitrary instances we are able to determine a within cubic time computable upper bound on the edit distance, which equals the minimized distance for infinitely many instances.