Retracted result on network equivalence reinstated | Science News

Support Science Journalism

Science News is a nonprofit.

Support us by subscribing now.

News in Brief

Retracted result on network equivalence reinstated

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

10:47am, January 11, 2017
two graphs

CONNECT THE DOTS  The graph isomorphism problem requires computers to quickly compare two graphs (shown) and determine if they are the same.

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

This article is only available to Science News subscribers. Already a subscriber? Log in now.
Or subscribe today for full access.

Get Science News headlines by e-mail.

More from Science News

From the Nature Index Paid Content