Graph Isomorphism Vanquished — Again

It’s been a whiplash-inducing couple of weeks for theoretical computer scientists. On January 4, László Babai, a professor at the University of Chicago, sent shock waves through the community by retracting a claim which, back in November 2015, researchers had hailed as the theoretical computer science advance of the decade. Then on January 9, Babai announced that he had fixed the flaw in his proof. And today, the mathematician who first spotted the error in Babai’s work — Harald Helfgott, of the University of Göttingen in Germany and France’s National Center for Scientific Research — publicly confirmed that the fix is correct, in a talk in Paris at the Bourbaki seminar, one of mathematics’ preeminent lecture series.

The back and forth concerns the graph isomorphism problem, which asks when two different-looking graphs — networks of nodes and edges — have the same underlying connectivity. Despite how simple the problem is to state, theoretical computer scientists have struggled for more than 30 years to figure out whether there is any computer algorithm that solves graph isomorphism efficiently.

Babai’s result presents an algorithm that solves graph isomorphism in a “quasi-polynomial” amount of time. Very roughly speaking, his algorithm carries the graph isomorphism problem almost all the way across the gulf between the problems that can’t be solved efficiently and the ones that can — it’s now splashing around in the shallow water off the coast of the efficiently-solvable problems, whose running time is what computer scientists call “polynomial.”

In the lead-up to these recent events, Helfgott had spent months studying the algorithm Babai announced in 2015, to prepare for his Bourbaki seminar. As Helfgott scrutinized the algorithm, he realized that it contained a subtle error in a step called the “Split-or-Johnson” procedure. This procedure involves simplifying a graph isomorphism problem by either identifying smaller “Johnson” graphs within the two graphs being compared, or finding a way to color the two graphs that respects their symmetries, making it easier to compare their structures.

The Split-or-Johnson procedure contained a recursive step, in which a certain subroutine split the problem into two smaller pieces and then called itself to run again on the smaller pieces. But each time the subroutine ran, it introduced a certain fudge factor into how accurately the colorings reflected the graphs’ symmetries, and these errors built up uncontrollably. In a procedure with this particular kind of error growth, “that ‘forking’ in the recursion is completely disastrous,” Helfgott wrote in an email.

Babai has now figured out how to make the subroutine call itself without forking into two branches at each step. “I am confident that the proof is correct,” Helfgott wrote to me.

Babai is working on a revised version of his paper, incorporating both this new fix and other edits in response to comments he has received about the paper over the course of the past year. He hopes to post a new draft online within about a month, he said by email.

To learn more about the graph isomorphism problem, read Erica Klarreich’s 2015 article “Landmark Algorithm Breaks 30-Year Impasse,” and her January 5 blog post, “Complexity Theory Problem Strikes Back.”

This article was reprinted in Spanish at Investigacionyciencia.es.