9
$\begingroup$

What is the fastest known undirected graph isomorphism algorithm?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Juho Sep 3 '14 at 13:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 3 '14 at 14:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 3 '14 at 14:47
  • 5
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 3 '14 at 14:54
  • 5
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Sep 3 '14 at 16:02
3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Purportedly runs in quasipolynomial time. Even if his analysis is flawed and it's merely subexponential, it will still be the fastest algorithm though. $\endgroup$ – Stella Biderman Mar 29 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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