A Primer on Graph Isomorphism

I spent 14 years on the faculty at the University of Chicago. I know László Babai well, we collaborated on some of my best known work. I also know Ryerson 251, a room where I've seen hundreds of talks and given more than a few myself. So I could imagine the excitement in that room on Tuesday as Babai gave the most anticipated talk in the history of theoretical computer science, the first of several talks Babai is giving on his new algorithm for graph isomorphism [Video]. Gabriel Gaster extensively live tweeted the event. Jeremy Kun has some details. Update (12/14): Paper now posted.

For this post instead of doing a bad job trying to overview Babai's proof, I'll explain the graph isomorphism problem and why it is important in the complexity world.

Suppose we have two high schools, say HS North and HS South, each with 1000 students. Consider a diagram (or graph) containing a point for each student at HS North with lines between students who are facebook friends, and a similar diagram for HS South. Is there a 1-1 map from the students at HS North to the students at HS South so that these diagrams look identical? That's the graph isomorphism problem.

To determine whether these two graphs were isomorphic you could look at all the possible mappings between students, but that's 1000! or more than 4x10²⁵⁶⁷ possible maps. There has long been known how to search a smaller number of possibilities, especially if we put some restrictions on the diagrams, but always exponential in n (the number of students) in the worst case. Ideally we'd like a polynomial-time algorithm and Babai gets very close, an algorithm that runs in time n^logkn time for some fixed k.

Graph Isomorphism is one of those few problems, like factoring, known to be in NP but not known to be in P or NP-complete. Graph non-isomorphism is the poster child for the class AM, the problems solved by a randomized verifier asking a single question to a powerful prover. Graph non-isomorphism in AM implies that Graph Isomorphism is not likely NP-complete and that under reasonable derandomization assumptions that Graph non-isomorphism is in NP. Kobler, Schöning and Toran wrote a whole book on the computational complexity issues of graph isomorphism.

Even small progress in graph isomorphism creates waves. At a theory conference in the late 80's a speaker caused a major stir when he casually mentioned he had a proof (he didn't) that Graph non-isomorphism was in NP. Babai's announced caused a huge tsunami and those of us who know him realize he wouldn't make such an announcement without being sure he has a proof. The talk put together a large number of ideas from combinatorics and graph theory. My impression is that those who saw the talk didn't leave convinced of the proof, but did feel Babai had found the pieces to make it work.

With Babai's breakthrough algorithm, the smart money says now that graph isomorphism sits in P. It took decades to get from quasipolynomial time to polynomial time for primality testing and the same time frame may be needed to get polynomial time for graph isomorphism. But it will likely happen and the complexity of graph isomorphism then gets a whole lot simpler.

A couple of thoughts: All the breakthrough results that I can remember were released as papers, ready to devour. This is the first result of this caliber I remember being announced as a talk.

Also we think of theory as a young person's game, most of the big breakthroughs coming from researchers early in their careers. Babai is 65, having just won the Knuth Prize for his lifetime work on interactive proofs, group algorithms and communication complexity. Babai uses his extensive knowledge of combinatorics and group theory to get his algorithm. No young researcher could have had the knowledge base or maturity to be able to put the pieces together the way that Babai did.

More on Babai and graph isomorphism from Scott, Luca, Bill, Tim, Dick and Ken, Reddit, Science News, New Scientist and Science.