*BibTeX*

@InProceedings{AKKV12approxgi, author = {V. Arvind and Johannes Köbler and Sebastian Kuhnert and Yadu Vasudev}, title = {Approximate Graph Isomorphism}, editor = {Branislav Rovan and Vladimiro Sassone and Peter Widmayer}, booktitle = {Mathematical Foundations of Computer Science (Proceedings of MFCS 2012)}, year = 2012, series = {LNCS}, number = 7464, publisher = {Springer}, address = {Berlin}, isbn = {978-3-642-32588-5}, doi = {10.1007/978-3-642-32589-2_12}, pages = {100-111}, }

**Approximate Graph
Isomorphism.**

With V. Arvind,
Johannes
Köbler, Yadu
Vasudev.

*Mathematical Foundations of Computer Science* (Proceedings
of 37th MFCS). Springer, 2012.
Pp. 100-111.

Abstract.We study optimization versions of Graph Isomorphism. Given two graphs

G_{1},G_{2}, we are interested in finding a bijection π fromV(G_{1}) toV(G_{2}) that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give ann^{O(log n)}time approximation scheme that for any constant factor α < 1, computes an α-approximation. We prove this by combining then^{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.