Complexity of simple undirected graph isomorphism problem

Question

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices.

My question:

1. What is the complexity of the best known algorithm for the simple undirected graph isomorphism problem?

I assume it should be a special case of the exponential algorithm by Babai et. al introduced in Canonical labeling of graphs.

As described in Reading List: Graph Isomorphism by Dave Bacon, this is not among the classes for which we have efficient algorithms. Thanks in advance for your answer.

Answer 1

László Babai. Graph Isomorphism in Quasipolynomial Time, 84 pages. [Version 1. Fri, 11 Dec 2015]

From Abstract :

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial $\exp ((\log n) ^ {O(1)}) $ time.

The best previous bound for GI was $ \exp ( O ( \sqrt {n\log n} ) ) ,$ where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $ \exp ( \tilde O ( \sqrt n ) ) ,$ where n is the size of the permutation domain (Babai, 1983)

Answer 2

Yes, the best known algorithm is still the algorithm from Babai and Luks, with runtime $\exp(O(\sqrt{n \log n}))$, where $n$ is the number of vertices in the graphs. Unless I'm mistaken, even the best known conondeterministic algorithm for graph isomorphism has exponential runtime. Babai and Luks' algorithm is plausibly near-optimal for deterministic algorithms, but there is much evidence that there is a polynomial time conondeterministic algorithm for graph isomorphism out there to be discovered. In particular, it is known that graph isomorphism is in coAM, and certain circuit lower bounds imply that coAM = coNP.