<p>László Babai. <a href="http://arxiv.org/pdf/1512.03547v1" rel="nofollow">Graph Isomorphism in Quasipolynomial Time</a>, 84 pages.  [Version 1.  Fri, 11 Dec 2015]</p>

<p>From <a href="http://arxiv.org/abs/1512.03547v1" rel="nofollow">Abstract</a> :</p>

<p><Blockquote>
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.</p>

<p>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)
</Blockquote></p>

CC BY-SA 3.0
2017-01-04T21:53:48.803Z
[Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.
Raphael
CC BY-SA 3.0
2015-12-24T09:03:22.980Z
2015-12-24T09:03:22.980Z
Yuriy V Dzyadyk
<p>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 <em>conondeterministic</em> 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 <a href="http://www.cs.umd.edu/~jkatz/complexity/f11/lecture17.pdf">known</a> that graph isomorphism is in coAM, and certain circuit lower bounds <a href="http://www.brics.dk/RS/99/47/BRICS-RS-99-47.pdf">imply</a> that coAM = coNP.</p>

CC BY-SA 3.0
2015-07-06T04:54:09.753Z
2015-07-06T04:54:09.753Z
William Hoza
<p>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.</p>

<p>My question:</p>

<ol>
<li>What is the complexity of the best known algorithm for the simple undirected graph isomorphism problem?</li>
</ol>

<p>I assume it should be a special case of the exponential algorithm by Babai et. al introduced in <a href="http://dl.acm.org/citation.cfm?id=808746" rel="nofollow">Canonical labeling of graphs</a>.</p>

<p>As described in <a href="http://dabacon.org/pontiff/?p=4148" rel="nofollow">Reading List: Graph Isomorphism</a> by Dave Bacon, this is not among the classes for which we have efficient algorithms. Thanks in advance for your answer.</p>

CC BY-SA 3.0
2015-07-06T11:42:00.760Z
I thought simple undirected graphs were the standard setting for graph isomorphism.
Sasho Nikolov
<cc.complexity-theory><graph-theory><graph-algorithms><graph-isomorphism><gr.group-theory>
Complexity of simple undirected graph isomorphism problem
Omar Shehab
# Complexity of simple undirected graph isomorphism problem

(Asked by: username_0 on 2015-07-05)

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](http://dl.acm.org/citation.cfm?id=808746).

As described in [Reading List: Graph Isomorphism](http://dabacon.org/pontiff/?p=4148) by Dave Bacon, this is not among the classes for which we have efficient algorithms. Thanks in advance for your answer.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, graph-isomorphism, gr.group-theory
> **Comments:**
> **username_1**: I thought simple undirected graphs were the standard setting for graph isomorphism.  

---

## 2 answers

### Answer by username_2 on 2015-12-24. Score: 2 | Accepted answer

László Babai. [Graph Isomorphism in Quasipolynomial Time](http://arxiv.org/pdf/1512.03547v1), 84 pages. [Version 1. Fri, 11 Dec 2015]

From [Abstract](http://arxiv.org/abs/1512.03547v1) :

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

> **Comments:**
> **username_3**: [Babai retracted the claim of quasipolynomial runtime](http://people.cs.uchicago.edu/~laci/update.html). Apparently there was an error in the analysis.  

---

### Answer by username_4 on 2015-07-06. Score: 6

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](http://www.cs.umd.edu/~jkatz/complexity/f11/lecture17.pdf) that graph isomorphism is in coAM, and certain circuit lower bounds [imply](http://www.brics.dk/RS/99/47/BRICS-RS-99-47.pdf) that coAM = coNP.


---

