Retracted result on network equivalence reinstated | Science News



Support credible science journalism.

Subscribe to Science News today.

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 available only to subscribing members. Join the Society today or Log in.

Get Science News headlines by e-mail.

More from Science News

From the Nature Index Paid Content