A Fast Graph Isomorphism Algorithm
While we wait for Laci
Today we want to discuss his talk, but
But we were not there. Nor were we able to send a GLL representative there to hear the talk. There are twitter feeds here and here. The former, by Gabriel Gaster, gives a running textual description, but otherwise we are still pretty in the dark as to the details of the algorithm.
Or are we?
A Fast Algorithm
There is old trick essentially due, I believe first, to Leonid Levin. This allows us to give a graph isomorphism algorithm that works almost in quasi-polynomial time—without seeing Laci’s algorithm. While we are in the dark I thought you might enjoy it.
Theorem: There is a concrete algorithm that runs in time and decides graph isomorphism correctly.
Here is any function that grows faster than any quasi-polynomial function—or at least faster than Laci’s function. For example,
Then the algorithm is:
Let and be vertex graphs. Run all Turing Machines of size less that for time. For each one test its output to see if it is an isomorphism. Suppose that is one of the outputs. Check whether is an isomorphism of to . If some one works say that and are isomorphic. If all fail say they are not.
Call this algorithm . If Laci’s theorem is correct, which we expect, then this algorithm works on all but a finite number of graph pairs. So fix those and make it .
So we can start running the algorithm without the details. Of course there are two problems. The first is that the running time here is huge—its a galactic algorithm. Second, its correctness relies on Laci’s theorem, and also we do not know when it starts to work. So it really is useless.
But it does show the power of Levin’s old idea.
Of course we must wait for Laci’s paper, which we hear is due out soon. And that is the key.