Complexity of simple undirected graph isomorphism problem 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:


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.
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.