History and status of the graph matching problem
From the paper Approximate Graph Isomorphism:


  We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $π$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log{n})}$ time approximation scheme that for any constant factor $α &lt; 1$, computes an $α$-approximation. We prove this by combining the $n^{O(\log{n})}$ time additive error approximation algorithm of Arora et al. [Math. Program., 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $α$-approximate for any constant factor $α$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.