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.

  • 11
    I thought simple undirected graphs were the standard setting for graph isomorphism. – Sasho Nikolov Jul 6 '15 at 11:42
up vote 2 down vote accepted

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)

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.

  • 4
    As far as I'm aware, "even the best known" bound on the quantum Merlin-Arthur $\hspace{.75 in}$ complexity of graph non-isomorphism is exponential. $\;$ – user6973 Jul 6 '15 at 5:14

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.