10

What is the fastest known undirected graph isomorphism algorithm?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
bbejot
  • 1,099
  • 6
  • 14
  • 2
    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 03 '14 at 13:29
  • 1
    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. – Kaveh Sep 03 '14 at 14:07
  • 1
    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 Sep 03 '14 at 14:47
  • 5
    @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 Sep 03 '14 at 14:54
  • 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 Sep 03 '14 at 15:07
  • 5
    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) – Marzio De Biasi Sep 03 '14 at 16:02

2 Answers2

3

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

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 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 Mar 29 '17 at 08: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) ) – Avi Tal Jan 26 '21 at 12:14
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 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.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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 03 '14 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. – David Richerby Nov 16 '14 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 '14 at 16:31
  • You seem to be confusing the statements "We haven't solved the problem yet" and "no progress has been made." – David Richerby Nov 16 '14 at 16:36