Three Hardness Results for Graph Similarity Problems
Notions of graph similarity provide alternative perspective on the graph isomorphism problem and vice-versa. In this paper, we consider measures of similarity arising from mismatch norms as studied in Gervens and Grohe: the edit distance $δ_{\mathcal{E}}$, and the metrics arising from $\ell_p$-operator norms, which we...
He Sun, Danny Vagnozzi
· Discrete Mathematics & Theor... · 0 citations