6

Has anyone implemented Laszlo Babai's quasi-polynomial graph isomorphism?

http://people.cs.uchicago.edu/~laci/

I am not an expert in this area. I am wondering why not just implement his algorithm and run it to verify its time complexity?

JackWM
  • 10,085
  • 22
  • 65
  • 92
  • 1
    I don't think it's been implemented yet (or rather: already), but bear in mind that the paper has not yet been validated by the usual round(s) of peer-review. But how would you "verify its time complexity" by running it? (in any case, "just implementing" his algorithm makes the task sound deceptively easy; I doubt it would be a simple matter) – Anthony Labarre May 24 '16 at 21:48
  • 3
    One frequent problem what people seem to forget is that if you have an algorithm with a running time of 10000000*(n^10000000) then it is a polynomial algorithm, which is absolutely useless *in practice*. Would you invest (=waste) your time on implementing something like this? In contrast, an algorithm with running time of 1/100000000*(1.1^n) might be quite efficient *in practice*. – Matsmath May 25 '16 at 07:58

2 Answers2

6

Let's imagine that you did implement the algorithm. Could you use that to verify the time complexity of that algorithm empirically?

Unfortunately, the answer is no. If we say that the time complexity of an algorithm is O(f(n)), then we're saying that

  • for sufficiently large inputs,
  • out of all possible inputs of that size,
  • the runtime is at most a constant multiple of n.

So imagine that we did code it up. To see whether the bound that's claimed actually applies, we could try running it on a few inputs and plotting the runtime, but that wouldn't tell us anything. Our inputs might not be "large enough" for the asymptotic upper-bound to apply. If we did get to a large input and we saw the runtimes on a number of different inputs, we still wouldn't know whether we had the worst-case runtime unless we tried all possible inputs, but the number of possible inputs to a graph isomorphism algorithm grows exponentially as a function of the size of the input. That means that we couldn't brute-force try all possible inputs at large sizes, so we'd never be sure whether we found the actual worst-case input. There are a number of algorithms like the simplex algorithm for linear programming that are known to be very fast except in rare pathological cases, so we'd always risk that the runtime wouldn't match what we expected.

There's also a lot of practical concerns that would arise. The theoretical analysis of algorithms often doesn't account for things like cache behavior, paging, thrashing, etc., so we might see certain large inputs take a much longer time than expected simply because they don't play well with caches. In that case, we might see things run much slower than expected even though the analysis of the number of primitive operations is correct.

In short, no amount of running the algorithm on practical inputs will ever let you confirm or deny that the runtime analysis is correct. If it seems to match the trend, that's great... but what about all the infinitely many inputs you didn't try looking at? If it doesn't seem to match the predicted trend, how do you know that you just haven't tried sufficiently large inputs? Or that you're seeing noise in the analysis from other factors?

This is why it's tough to analyze algorithms like these. For all we know, we already have a polynomial time algorithm for graph isomorphism, but no one has been able to prove that it has the right runtime. No amount of empirical data will work as a proof, though it might motivate people to try to prove that a particular approach runs quickly as a way of theoretically justifying the observed runtime.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • "For all we know, we already have a polynomial time algorithm for graph isomorphism, but no one has been able to prove that it has the right runtime." Can you please mention the name of the algorithm you are referring to here? – Jim C Jul 24 '18 at 12:29
  • @JimC Alas, I didn’t have a specific algorithm in mind when writing that statement. It’s entirely possible that some algorithm that someone’s developed somewhere actually by pure coincidence happens to be a polynomial-time algorithm for graph isomorphism, but that we haven’t been able to prove it. – templatetypedef Jul 24 '18 at 15:18
0

Practical graph isomorphism is in P. See Brendan McKay's C implementation of nauty.

nauty and Traces are programs for computing automorphism groups of graphs and digraphs. They can also produce a canonical labelling. nauty and Traces are written in a portable subset of C, and run on a considerable number of different systems.

Babai's result is only of theoretical interest.

Matsmath
  • 1,164
  • 2
  • 21
  • 40
  • I heard [VF2](http://lalg.fri.uni-lj.si/pub/amalfi/vflib2/src/) is also quite _efficient_, but I didn't see a comparison between _nauty_ and _VF2_. Did I miss anything? – JackWM May 24 '16 at 22:45
  • Could you define "practical" and point us to a reference that gives the specific polynomial time complexity of McKay's canonical labeling algorithm? – Anthony Labarre May 25 '16 at 07:06
  • 1
    There are clever hand-constructions of series of graphs for which *nauty*'s running time is exponential. But these graphs are rare. See [McKay1](http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf) [McKay2](http://arxiv.org/abs/1301.1493) and [complexity](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.3532) and [some explanation from CS.SE](http://cstheory.stackexchange.com/a/3143) and some (vague) answer/explanation from [SO](http://stackoverflow.com/a/27001051/4068338). – Matsmath May 25 '16 at 07:44
  • @JackWM If you want to play with different algorithms, and you have Mathematica, check out the [IGraph/M package](https://github.com/szhorvat/IGraphM). It provides the VF2, Bliss and LAD algorithms. In addition there's Mathematica's built-in, which *I think* uses nauty (or at least nauty is acknowledged in the credits). For large and hard problems, Bliss is by far the most efficient in practice. – Szabolcs Jun 22 '16 at 16:32
  • 2
    -1: A guaranteed quasi-polynomial time solution to graph isomorphism is most certainly *not* "only of theoretical interest". – Hans Brende May 02 '22 at 17:08