What did Babai Do? The short answer is Johnson graphs. Assuming his claims are correct, all of the open graph isomorphism challenges are simply embedded Johnson graphs.

Several popular science sources have published the news that László Babai at the University of Chicago has found a new Graph Isomorphism (GI) algorithm. These widespread reports often include the claim that this GI algorithm is “quasi-polynomial”, but the details on the algorithm itself have been scant.

Given the reasonable academic obligations to validate his proof, Prof. Babai has been slow to release the details. As a consequence, publicly available information about algorithm has been limited to Prof. Babai’s lectures at the University of Chicago. The first of these has been released on YouTube (Graph Isomorphism in Quasipolynomial Time). Although the 2 hour video is inadequate for the complete algorithm and its complexity proof, Prof. Babai provides a clear outline of his method and its complexity.

Prof. Babai builds on Luks’s work on GI from the 1980s. Luks’s work uses a divide-and-conquer strategy to perform subgraph GI using individualization and equipartition graphs. However, these two strategies do not handle all possible graphs. Due to these “partition resistant” graphs, Luks’s upper bound is (exp(sqrt(n * log(n))).

Prof. Babai claims that the only graphs that resist individualization and equipartitioning are Johnson graphs. His split-or-Johnson algorithm reveals any embedded Johnson graphs. Once the embedded Johnson graphs are revealed, they dramatically reduce the complexity of GI problem for sub-graphs. This insight is Prof. Babai’s brilliant breakthrough.

The details of this split-or-Johnson (soJ) algorithm remain for future videos. Validating this algorithm will be an essential part of validating the Johnson graph claim. Assuming the soJ algorithm is valid and provides the expected computational bounds, the GI problem has quasipolynomial (exp((log n)O(1))) complexity.

In practice, this seems to mean that any GI problem can be solved through divide-and-conquer with these three strategies:

1. Match embedded individualized graph
2. Match embedded equipartitioned graph
3. Match embedded Johnson graph

In each case, the sub-problems scale slower then their partitioning and progress can be guaranteed.

It’s a very nice result, and very believable. Even if some gap or exceptional embedded graph case is discovered, it remains a huge advance on graph isomorphism.

• Next Post
• Prev Post