<p><a href="https://people.cs.uchicago.edu/%7Elaci/update.html" rel="nofollow noreferrer">Babai invented</a> the fastest known algorithm which runs in quasipolynomial time <span class="math-container">$2^{(\log n)^{O(1)}}$</span>.</p>

CC BY-SA 3.0
2017-03-29T08:59:35.997Z
Purportedly runs in quasipolynomial time. Even if his analysis is flawed and it's merely subexponential, it will still be the fastest algorithm though.
Stella Biderman
CC BY-SA 4.0
2021-01-26T12:14:09.527Z
Maybe it is worthwhile to put prentices around the log... I.e. 2^( (logn)^O(1) ), or more precisely 2^( O( (log n)^3) )
Avi Tal
CC BY-SA 4.0
2017-03-29T06:27:18.190Z
2021-01-28T11:28:02.420Z
2021-01-28T11:28:02.420Z
Mohammad Al-Turkistany
<p>research on graph isomorphism has generally gone in the direction of looking at efficient or improved algorithms for many special graph classes with P-Time algorithms for which there has been much progress, and also more empirical analysis with state-of-the-art software eg <a href="http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml" rel="nofollow">Nauty</a> looking somewhat at average and worst case behaviors separately. for the general problem according to this <a href="http://dabacon.org/pontiff/?p=4148" rel="nofollow">blog survey</a> by <a href="http://dabacon.org/pontiff/?page_id=5938" rel="nofollow">Bennett/ Flammia/ Harrow</a> apparently an old result by Babai/Luks may be the best known.</p>

<blockquote>
  <p>“Canonical labeling of graph” by László Babai and Eugene M. Luks STOC 1983 (<a href="http://dl.acm.org/citation.cfm?id=808746" rel="nofollow">paper here</a>)
  This describes a subexponential (or, err, what did Scott decide to call this?), exp(-n^{frac{1}{2}+c}), time algorithm for a graph with n vertices.  Now as a reading list I don’t recommend jumping into this paper quite yet, but I just wanted to douse your optimism for a classical algorithm by showing you (a) the best we have in general is a subexponential time algorithm, (b) that record has stood for nearly three decades, and (c) that if you look at the paper you can see it’s not easy.  Abandon hope all ye who enter?</p>
</blockquote>

<p>here are two other fairly comprehensive surveys to gauge state-of-the-art but maybe more with an empirical slant.</p>

<ul>
<li><p><a href="http://www.diatel.upm.es/jllopez/tesis/thesis.pdf" rel="nofollow">Efficient Algorithms for Graph Isomorphism Testing</a> Jose Luis Lopez Presa PhD thesis (2009)</p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9419" rel="nofollow">The Graph Isomorphism Problem (1996)</a> Fortin (1996)</p></li>
</ul>

CC BY-SA 3.0
2014-11-16T16:15:56.853Z
Note that the Fortin survey is nearly 20 years old, which is an eternity in a field where, for example, the concept of NP-completeness is only about 40 years old.
David Richerby
CC BY-SA 3.0
2014-11-16T16:31:32.527Z
yes, noted that also, but there is also the phenomenon of TCS key/ hard open problems showing little major progress over decades, obviously also including P vs NP as a canonical example of that, and GI fits also as stated.
vzn
CC BY-SA 3.0
2014-11-16T16:36:10.573Z
You seem to be confusing the statements "We haven't solved the problem yet" and "no progress has been made."
David Richerby
CC BY-SA 3.0
2014-09-03T17:27:36.160Z
another point is that as in JGs answer, Graph-Isomorphism has deep theoretical links to Group-Isomorphism problem. this can be seen in this other blog on subj by RJLipton, [An approach to graph isomorphism](http://rjlipton.wordpress.com/2009/05/04/an-approach-to-graph-isomorphism/)
vzn
CC BY-SA 3.0
2014-09-03T15:36:09.657Z
2014-09-03T15:49:42.643Z
2014-09-03T15:49:42.643Z
vzn
<p>What is the fastest known undirected graph isomorphism algorithm?</p>

CC BY-SA 3.0
2014-09-03T13:29:49.000Z
I think it's better if you just ask for the fastest known algorithm, and not the correctness of the algorithm given in the paper (in particular, see [the relevant meta question](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics)). To me, the abstract is already a red flag (the conclusions seem to contain false information as well).
Juho
CC BY-SA 3.0
2014-09-03T14:07:52.137Z
Generally if a major result for a famous problem is correct it would appear on famous theory blogs [1](http://blog.computationalcomplexity.org) [2](http://rjlipton.wordpress.com) and on [the Wikipedia article for the problem](http://en.m.wikipedia.org/wiki/Graph_isomorphism_problem).
Kaveh
CC BY-SA 3.0
2014-09-03T14:47:25.490Z
The paper does not pass the smell test. It purports to solve a major problem but appeared at an obscure conference. There are no proofs. Correctness is "validated" experimentally. The authors think that graph isomorphism is NP-hard.
Sasho Nikolov
CC BY-SA 3.0
2014-09-03T14:54:38.347Z
@JoshuaGrochow says the fastest known algorithm takes time $2^{\sqrt{n\log n}}$ in this answer http://cstheory.stackexchange.com/a/22059/4896. I think the algorithm is deterministic.
Sasho Nikolov
CC BY-SA 3.0
2014-09-03T15:07:48.657Z
re Ks comment, there is a period/ window where new correct algorithms/ rumors appear possibly in cyberspace 1st and have not yet been evaluated by experts. the evaluation by experts cannot be instantaneous. agreed graph isomorphism is a high profile problem with many incorrect claims/ papers. K has stated emphatically/ repeatedly wrt the (now frozen) meta question/ policy this site is not a place for evaluation of new breakthrough claims and there is apparently/ generally no significant opposing faction on this issue on the site... [chat] is a possible alternative venue for discussion...
vzn
CC BY-SA 3.0
2014-09-03T16:02:55.103Z
According to two recent works on the subject: [Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity - 2014](http://arxiv.org/abs/1408.3510) and [Approximate Graph Isomorphism - 2012](http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_12) the current fastest algorithm has running time $2^{O(\sqrt {n \log n})}$ on n-vertex graphs (result by Babai and Luks, 1983)
Marzio De Biasi
<cc.complexity-theory><reference-request><graph-algorithms><graph-isomorphism>
Fastest known deterministic algorithm for the undirected Graph Isomorphism problem
bbejot
# Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

(Asked by: username_0 on 2014-09-03)

What is the fastest known undirected graph isomorphism algorithm?

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, graph-isomorphism

> **Comments:**
> **username_1**: I think it's better if you just ask for the fastest known algorithm, and not the correctness of the algorithm given in the paper (in particular, see [the relevant meta question](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics)). To me, the abstract is already a red flag (the conclusions seem to contain false information as well).  
> **username_2**: Generally if a major result for a famous problem is correct it would appear on famous theory blogs [1](http://blog.computationalcomplexity.org) [2](http://rjlipton.wordpress.com) and on [the Wikipedia article for the problem](http://en.m.wikipedia.org/wiki/Graph_isomorphism_problem).  
> **username_3**: The paper does not pass the smell test. It purports to solve a major problem but appeared at an obscure conference. There are no proofs. Correctness is "validated" experimentally. The authors think that graph isomorphism is NP-hard.  
> **username_3**: @JoshuaGrochow says the fastest known algorithm takes time $2^{\sqrt{n\log n}}$ in this answer http://cstheory.stackexchange.com/a/22059/4896. I think the algorithm is deterministic.  
> **username_4**: re Ks comment, there is a period/ window where new correct algorithms/ rumors appear possibly in cyberspace 1st and have not yet been evaluated by experts. the evaluation by experts cannot be instantaneous. agreed graph isomorphism is a high profile problem with many incorrect claims/ papers. K has stated emphatically/ repeatedly wrt the (now frozen) meta question/ policy this site is not a place for evaluation of new breakthrough claims and there is apparently/ generally no significant opposing faction on this issue on the site... [chat] is a possible alternative venue for discussion...  
> **username_5**: According to two recent works on the subject: [Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity - 2014](http://arxiv.org/abs/1408.3510) and [Approximate Graph Isomorphism - 2012](http://link.springer.com/chapter/10.1007%2F978-3-642-32589-2_12) the current fastest algorithm has running time $2^{O(\sqrt {n \log n})}$ on n-vertex graphs (result by Babai and Luks, 1983)  

---

## 2 answers

### Answer by username_6 on 2017-03-29. Score: 3

[Babai invented](https://people.cs.uchicago.edu/%7Elaci/update.html) the fastest known algorithm which runs in quasipolynomial time $2^{(\log n)^{O(1)}}$.

> **Comments:**
> **username_7**: Purportedly runs in quasipolynomial time. Even if his analysis is flawed and it's merely subexponential, it will still be the fastest algorithm though.  
> **username_8**: Maybe it is worthwhile to put prentices around the log... I.e. 2^( (logn)^O(1) ), or more precisely 2^( O( (log n)^3) )  

---

### Answer by username_4 on 2014-09-03. Score: 2

research on graph isomorphism has generally gone in the direction of looking at efficient or improved algorithms for many special graph classes with P-Time algorithms for which there has been much progress, and also more empirical analysis with state-of-the-art software eg [Nauty](http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml) looking somewhat at average and worst case behaviors separately. for the general problem according to this [blog survey](http://dabacon.org/pontiff/?p=4148) by [Bennett/ Flammia/ Harrow](http://dabacon.org/pontiff/?page_id=5938) apparently an old result by Babai/Luks may be the best known.

> “Canonical labeling of graph” by László Babai and Eugene M. Luks STOC 1983 ([paper here](http://dl.acm.org/citation.cfm?id=808746))
> This describes a subexponential (or, err, what did Scott decide to call this?), exp(-n^{frac{1}{2}+c}), time algorithm for a graph with n vertices. Now as a reading list I don’t recommend jumping into this paper quite yet, but I just wanted to douse your optimism for a classical algorithm by showing you (a) the best we have in general is a subexponential time algorithm, (b) that record has stood for nearly three decades, and (c) that if you look at the paper you can see it’s not easy. Abandon hope all ye who enter?

here are two other fairly comprehensive surveys to gauge state-of-the-art but maybe more with an empirical slant.

* [Efficient Algorithms for Graph Isomorphism Testing](http://www.diatel.upm.es/jllopez/tesis/thesis.pdf) Jose Luis Lopez Presa PhD thesis (2009)
* [The Graph Isomorphism Problem (1996)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9419) Fortin (1996)

> **Comments:**
> **username_4**: another point is that as in JGs answer, Graph-Isomorphism has deep theoretical links to Group-Isomorphism problem. this can be seen in this other blog on subj by RJLipton, [An approach to graph isomorphism](http://rjlipton.wordpress.com/2009/05/04/an-approach-to-graph-isomorphism/)  
> **username_9**: Note that the Fortin survey is nearly 20 years old, which is an eternity in a field where, for example, the concept of NP-completeness is only about 40 years old.  
> **username_4**: yes, noted that also, but there is also the phenomenon of TCS key/ hard open problems showing little major progress over decades, obviously also including P vs NP as a canonical example of that, and GI fits also as stated.  
> **username_9**: You seem to be confusing the statements "We haven't solved the problem yet" and "no progress has been made."  

---

