@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₁,G₂, we are interested in finding a bijection π from V(G₁) to V(G₂) 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.