Skip to content

A Fast Graph Isomorphism Algorithm

November 11, 2015


While we wait for Laci {\dots}

László Babai just gave his first talk on his new graph isomorphism (GI) algorithm. The photo was taken at the talk and posted by several people.
BabaiCloseup

Today we want to discuss his talk, but {\dots}

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 {\cal A} that runs in time {g(n)} and decides graph isomorphism correctly.

Here {g(n)} is any function that grows faster than any quasi-polynomial function—or at least faster than Laci’s function. For example,

\displaystyle g(n) = 2^{\log^{\log^{*}(n)}(n)}.

Then the algorithm is:

Let {G} and {H} be {n} vertex graphs. Run all Turing Machines of size less that {g(n)} for {g(n)} time. For each one test its output to see if it is an isomorphism. Suppose that {\pi} is one of the outputs. Check whether {\pi} is an isomorphism of {G} to {H}. If some one works say that {G} and {H} are isomorphic. If all fail say they are not.

Call this algorithm {\cal B}. 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 {\cal A}.

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.

Open Problems

Of course we must wait for Laci’s paper, which we hear is due out soon. And that is the key.

23 Comments leave one →
  1. November 11, 2015 7:28 am

    Where you wrote \log(n)^{\log*(n)}, I believe you meant to write exp(\log(n)^{\log*(n)})

  2. rjlipton permalink*
    November 11, 2015 9:18 am

    Noah

    Thanks, and of course.

    dick

  3. November 12, 2015 12:28 pm

    the statement “without seeing his algorithm” is a bit problematic! amusing as always, but whats the fine print—your “theorem” assumes his proof has some quasipolynomial Dtime function right? how about a human readable interpretation? “for any algorithm that runs in time f(n), there is another one that runs ‘slightly’ faster, but is galactic,” to borrow one of your own terms…?

  4. chirpchirp permalink
    November 12, 2015 5:00 pm

    Jeremy Kun wrote a blog post giving an overview of the first talk at

    http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

  5. November 12, 2015 5:22 pm

    Sorry, but I understand nothing about the {}“problem” of string
    isomorphism. The definition of graph isomorphism is: $G=P^{-1}G^{\prime}P$,
    where $G$ and $G^{\prime}$ are adjacent matrices of given graphs;
    $P$ is permitation matrix. So, we can imagine the same definition
    for string isomorphism, where $G$ and $G^{\prime}$ are strings (vectors).
    For example, a string {}“adcb” and a string {}“badc” are isomorphic.
    But, there is significant difference in the definitions: adjacent
    matrix is 2D (two dimension) structure, string (vector) is 1D structure:
    we know how to sort 1D structure, but we do not know how to sort a
    matrix.

    Theorem: we can sort vector for polynomial time.

    Proof: See buble sort in wiki.

    The strings {}“adcb” and {}“badc” have trivial canonical form:
    {}“abcd”, similar form is not obvious for graphs.

    I only want to say that in contrast with graph isomorphism problem,
    the string isomorphism {}“problem” is trivial problem.

  6. November 13, 2015 8:18 am

    A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

  7. November 13, 2015 9:53 am

    Drs. Reagan and Lipton, your commentary is very appreciated, it is all well and good, but maybe you could also invite other experts, like C. BERKHOLZ or MARTIN GROHE to comment.

  8. John permalink
    November 17, 2015 4:42 pm

    [video src="http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4" /]

  9. John permalink
    November 17, 2015 4:44 pm

    I think a post on Eugene Luks’ algorithm for group isomorphism would be nice.

  10. slt permalink
    November 18, 2015 4:52 pm

    I am not a computer scientist, and have not thought about graph isomorphism before, but thinking about it naively it does not seem to be a hard problem. Given graphs G and H there are obvious checks on their degree sequences that can immediately be evidence that they are not isomorphic. Then one can look at degree sequences of the powers of these graphs G^k and H^k for k = 2, 3, 4… If those types of checks all pass, then one can look at the spectrum of the adjacency matrices of G and H (and perhaps their powers as well). For if the graphs are isomorphic then the spectrums of their adjacency matrices are identical. Eigenvalue computation is a O(N^3) problem. It would have to be a pretty weird conspiracy to have two graphs which are not isomorphic to have the same spectrum (or the spectrum of the powers of those graphs).

    • November 19, 2015 2:11 am

      slt,
      “Weird conspiracies” happen all the time in math/computer science🙂.

      • slt permalink
        November 19, 2015 2:33 am

        I agree with that in general, but for this particular problem can you give examples of families of pairs of graphs which are non-isomorphic but have the same spectrum? Maybe that will shed some light as to why this is a difficult problem.

      • slt permalink
        November 19, 2015 12:54 pm

        I found a paper that goes into this topic:
        https://cs.anu.edu.au/people/Brendan.McKay/papers/GodsilMcKayCospectral.pdf
        The “conspiracy” is not particularly deep. Very interesting stuff.

      • slt permalink
        November 19, 2015 5:52 pm

        Example 2.3 (a) in the above paper is interesting. There are two non-isomorphic graphs on 9-vertices (call them G and H) that have the same spectrum and the same degree sequence. However the degree sequence of G^2 and H^2 is already different. Maybe looking at the degree sequence of a high power of the graphs is a better discriminant than looking at their spectrum.

        I bet someone has found a pair of graphs that are non-isomorphic but have the same degree sequence for all powers. Kind of like the situation with the Fermat primality test and Carmichael numbers. Alright I will stop polluting your blog.

    • November 21, 2015 5:26 pm

      There is a lot of non-isomorphic cospectral graphs (http://mathworld.wolfram.com/CospectralGraphs.html).

  11. Jhon Hard permalink
    November 20, 2015 1:52 pm

    P = NP problem (proven)

    P=NP, in the factorization of all odd number.

    See: http://www.ijma.info Vol 6 (9) 2015

  12. November 21, 2015 5:32 pm

    Again, I see [video src="http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4" /], but I do not understand why GI may be reduced to string isomorphism?

  13. DPM permalink
    December 19, 2015 5:49 am

    The algorithm for Isomorphism of the order of the cube of the number of edges is here guys!

    http://vixra.org/pdf/1512.0322v1.pdf

  14. DPM permalink
    December 20, 2015 1:54 am

    Please note that the above referenced Isomorphism condition:

    http://vixra.org/pdf/1512.0322v1.pdf

    is applicable to strongly regular graphs. For other graphs it is not directly applicable and in that case one needs to arrange first the vertices in nonincreasing degree sequence and then label the vertices with labels {1, 2, …., p} and one need to apply transpositions among vertices with same degree for conclusively implying nonisomorphism when we cannot identify next edge labels without disturbing earlier identified edge labels.

    DPM

  15. DPM permalink
    December 21, 2015 6:24 am

    Please refer to Isomorphism checking algorithm at:

    http://vixra.org/pdf/1512.0322v2.pdf

    Thank you, DPM

Trackbacks

  1. A Fast Graph Isomorphism Algorithm « Pink Iguana
  2. How to Cite a Blog Comment in APA Style

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s