Jul 2026
On the Complexity of Graph Edit Distance in Restricted Graph Classes
It is proved that both the maximum common edge subgraph and the graph edit distance remain NP-hard, even when both graphs are paths, even when one graph is a path and the other is a tree.
Maximilian Limmer, Nils M. Kriege
· arXiv.org · 0 citations