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.