Testing Isomorphism in the Bounded-Degree Graph Model
Webpage for a paper by Oded Goldreich
Abstract
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:
- The query complexity of testing isomorphism to a fixed object
(i.e., an $n$-vertex graph or an $n$-long sequence)
is ${\widetilde{\Theta}}(n^{1/2})$.
- The query complexity of testing isomorphism between two input objects
is ${\widetilde{\Theta}}(n^{2/3})$.
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.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.