On the Complexity of Graph Edit Distance in Restricted Graph Classes

Maximilian Limmer, Nils M. Kriege

The graph edit distance generalizes several well-known NP-hard problems and is therefore NP-hard itself. However, the relationship between the considered graph class, the edit cost…