SAME GRAPH, DIFFERENT SHAPE These two graphs might look different, but each circle on the first graph corresponds to one on the second, connecting to the same other circles. Mathematicians call the graphs “isomorphic.” This year, computer scientist László Babai presented an algorithm that could overcome computers' longstanding difficulty in comparing such graphs.
E. Otwell
The fraternity of problems that confound computers has lost a prominent member. Computer scientist László Babai presented a new algorithm this year that efficiently tackles the graph isomorphism problem. It’s a type of problem that computers struggle to solve, even though a solution provided in advance is easily verified. Assuming it is confirmed, says Stanford theoretical computer scientist Ryan Williams, this is the biggest advance in the field in more than a decade.
The problem requires computers to compare two graphs, or networks of connected points, and determine whether all points are linked in the same way. Previously, the time required to solve the problem rose nearly exponentially with graph size. Babai’s algorithm, born from decades of mathematical effort, keeps the required computing time under control by solving even the hardest cases in what’s called quasipolynomial time (SN: 12/12/15, p. 6). Babai’s proof may provide insights for factoring large numbers and cracking other problems with easy-to-check, hard-to-solve status.
