Approximate Graph Isomorphism

Abstract 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 α < 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.

Authors

• Vikraman Arvind
• Johannes Köbler
• Sebastian Kuhnert
• Yadu Vasudev

Keywords

No keywords are indexed for this paper.