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
