Testing Graph Isomorphism

Two graphs $G$ and $H$ on $n$ vertices are $\epsilon$-far from being isomorphic if at least $\epsilon\binom{n}{2}$ edges must be added or removed from $E(G)$ in order to make $G$ and $H$ isomorphic. In this paper we deal with the question of how many queries are required to distinguish between the case that two graphs are isomorphic and the case that they are $\epsilon$-far from being isomorphic. A query is defined as probing the adjacency matrix of any one of the two graphs, i.e., asking if a pair of vertices forms an edge of the graph or not. We investigate both one-sided and two-sided error testers under two possible settings: The first setting is where both graphs need to be queried, and the second setting is where one of the graphs is fully known to the algorithm in advance. We prove that the query complexity of the best one-sided error testing algorithm is $\widetilde{\Theta}(n^{3/2})$ if both graphs need to be queried, and that it is $\widetilde{\Theta}(n)$ if one of the graphs is known in advance (where the $\widetilde{\Theta}$ notation hides polylogarithmic factors in the upper bounds). For two-sided error testers, we prove that the query complexity of the best tester is $\widetilde{\Theta}(\sqrt{n})$ when one of the graphs is known in advance, and we show that the query complexity lies between $\Omega(n)$ and $\widetilde{O}(n^{5/4})$ if both $G$ and $H$ need to be queried. All of our algorithms are additionally nonadaptive, while all of our lower bounds apply for adaptive testers as well as nonadaptive ones.