Solution to ‘graph isomorphism’ problem restored after error is found
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