Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

What is the fastest known undirected graph isomorphism algorithm?

• 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). To me, the abstract is already a red flag (the conclusions seem to contain false information as well).
– Juho
Sep 3, 2014 at 13:29
• Generally if a major result for a famous problem is correct it would appear on famous theory blogs 1 2 and on the Wikipedia article for the problem. Sep 3, 2014 at 14:07
• 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. Sep 3, 2014 at 14:47
• @JoshuaGrochow says the fastest known algorithm takes time $2^{\sqrt{n\log n}}$ in this answer cstheory.stackexchange.com/a/22059/4896. I think the algorithm is deterministic. Sep 3, 2014 at 14:54
• According to two recent works on the subject: Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity - 2014 and Approximate Graph Isomorphism - 2012 the current fastest algorithm has running time $2^{O(\sqrt {n \log n})}$ on n-vertex graphs (result by Babai and Luks, 1983) Sep 3, 2014 at 16:02

2 Answers

Babai invented the fastest known algorithm which runs in quasipolynomial time $$2^{(\log n)^{O(1)}}$$.

• Purportedly runs in quasipolynomial time. Even if his analysis is flawed and it's merely subexponential, it will still be the fastest algorithm though. Mar 29, 2017 at 8:59
• Maybe it is worthwhile to put prentices around the log... I.e. 2^( (logn)^O(1) ), or more precisely 2^( O( (log n)^3) ) Jan 26, 2021 at 12:14

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 looking somewhat at average and worst case behaviors separately. for the general problem according to this blog survey by Bennett/ Flammia/ Harrow 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) 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.

• 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
– vzn
Sep 3, 2014 at 17:27
• 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. Nov 16, 2014 at 16:15
• 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
Nov 16, 2014 at 16:31
• You seem to be confusing the statements "We haven't solved the problem yet" and "no progress has been made." Nov 16, 2014 at 16:36