Retracted result on network equivalence reinstated | Science News


Help us keep you informed.

Real Science. Real News.

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