Robust Graph Isomorphism, Quadratic Assignment and VC Dimension

Anatole Dahan, Martin Grohe, Daniel Neuen +1

We present an additive $\epsilon n^2$-approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension $d$ running in time $n^{O(d/\varepsilon^{2})}…