Retracted result on network equivalence reinstated
Solution to ‘graph isomorphism’ problem restored after error is found
CONNECT THE DOTS The graph isomorphism problem requires computers to quickly compare two graphs (shown) and determine if they are the same.
E. Otwell
A computer scientist has taken his colleagues on a rollercoaster ride.
In the span of several days, László Babai of the University of Chicago walked back his earlier claim of making a major advance on a classic puzzle of computer science, only to reinstate it after fixing an error in his work.
At issue is the problem of “graph isomorphism,” which demands that a computer determine if two networks of interconnected points, or “graphs,” are equivalent. For simple graphs, this task is quick, but complex ones could be time consuming for a computer to crunch through.
In November 2015, Babai reported at a meeting in Chicago that he had created an algorithm that solved the graph isomorphism problem much faster than was previously possible (SN: 12/12/15, p. 6). Using the previous best algorithm, the time the task takes balloons almost exponentially as the graphs increase in complexity, quickly becoming unwieldy. But Babai’s method operates in what’s known as “quasipolynomial time,” which means graphs can be compared within a time period that grows more slowly with complexity.
In an announcement on his website on January 4, Babai reported that mathematician Harald Helfgott of the University of Göttingen in Germany had reviewed the result and found an error. As a result, Babai downgraded his claim to a smaller speedup. That demotion didn’t last long: On January 9, Babai announced on his website that he had fixed the problem.
Despite the flip-flopping, the independent review of the work has increased some researchers’ confidence in the result. “I’m more convinced that it’s correct than I was before,” says MIT computer scientist Ryan Williams. But, he says, as Babai has yet to publish the new result, “there’s not a whole lot to go on right now.”
