Testing Isomorphism in the Bounded-Degree Graph Model

摘要

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs. We essentially determine the query complexity of these testing problems in the special case of n -vertex graphs with connected components of size at most poly ( log n ) . This is done by showing that these problems are computationally equivalent (up to polylogarithmic factors) to corresponding problems regarding isomorphism between sequences (over a large alphabet). Ignoring the dependence on the proximity parameter, our main results are: egin{enumerate} item The query complexity of testing isomorphism to a fixed object (i.e., an n -vertex graph or an n -long sequence) is ( n 1 2 ) . item The query complexity of testing isomorphism between two input objects is ( n 2 3 ) . end{enumerate} Testing isomorphism between two sequences is shown to be related to testing that two distributions are equivalent, and this relation yields reductions in three of the four relevant cases. Failing to reduce the problem of testing the equivalence of two distribution to the problem of testing isomorphism between two sequences, we adapt the proof of the lower bound on the complexity of the first problem to the second problem. This adaptation constitutes the main technical contribution of the current work. Determining the complexity of testing graph isomorphism (in the bounded-degree graph model), in the general case (i.e., for arbitrary bounded-degree graphs), is left open.