# Retracted result on network equivalence reinstated

## Solution to ‘graph isomorphism’ problem restored after error is found

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