Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-102 | 11th August 2019 16:36

Testing Isomorphism in the Bounded-Degree Graph Model

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 11th August 2019 16:36
Downloads: 760
Keywords: 


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:
\begin{enumerate}
\item
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})$.
\item
The query complexity of testing isomorphism between two input objects is ${\widetilde{\Theta}}(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.



Changes to previous version:

Adding a relevant reference that was missed by mistake.


Paper:

TR19-102 | 10th August 2019 19:22

Testing Isomorphism in the Bounded-Degree Graph Model





TR19-102
Authors: Oded Goldreich
Publication: 10th August 2019 19:22
Downloads: 1077
Keywords: 


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:
\begin{enumerate}
\item
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})$.
\item
The query complexity of testing isomorphism between two input objects is ${\widetilde{\Theta}}(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.



ISSN 1433-8092 | Imprint