We study optimization versions of Graph Isomorphism. Given two graphs G1G2 , we are interested in finding a bijection from V(G1) to V(G2) that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an nO(logn) time approximation scheme that for any constant factor 1, computes an -approximation. We prove this by combining the nO(logn) 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.

We also explore these optimization problems for bounded color class graphs which is a well studied tractable special case of Graph Isomorphism. Surprisingly, the bounded color class case turns out to be harder than the uncolored case in the approximate setting.