Abstract. We study optimization versions of Graph Isomorphism. Given two graphs G1, G2, 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 n O(log n) time approximation scheme that for any constant factor α < 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. 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.
In particular, REF showed that various versions of this problem are NP-hard to approximate to within a constant factor.
Approximate Graph Isomorphism ⋆
MFCS
Mathematics Computer Science