New algorithm cracks graph problem

A puzzle that has long flummoxed computers and the scientists who program them has suddenly become far more manageable.

A new algorithm efficiently solves the graph isomorphism problem, computer scientist László Babai announced November 10 at a Combinatorics and Theoretical Computer Science seminar at the University of Chicago. The problem requires determining whether two separate sets of interconnected points, known as graphs, are linked in the same way even if the graphs look very different. In practice, existing algorithms can do the job in reasonable time, but it was possible that extremely complex graphs would make the problem intractable. Not anymore.

“My first thought was that this was a joke. I checked the month to make sure it wasn’t April,” says Ryan Williams, a Stanford University computer scientist. “It’s a huge jump in our understanding of the problem.” He says the discovery is potentially the most important theoretical computer science advance in more than a decade.

Babai’s algorithm still needs to be vetted, but his expertise gives colleagues confidence in the result: He was grappling with the problem even before he made it the topic of his 1984 doctoral thesis. While the problem may seem abstract, it’s a prominent example of a strange class of puzzles that computers have trouble solving despite being able to quickly verify a solution if one is provided. The result could also reverberate beyond computer science, such as allowing chemists to determine whether complex molecules have the same bonding structure.

In math terminology, “graph” is a fancy word for a network, the kind of diagram that depicts, for instance, a web of friends on Facebook or the spread of a disease. Each point, or node, is like a ping-pong ball that’s indistinguishable from any other ball and connects to one or more balls with string. With such a setup it’s easy to make two initially identical graphs look very different by shifting the balls around (see diagram). The graph isomorphism problem requires a computer to examine two graphs that may look very different and determine whether all the balls share the same connections. Graphs that share this relationship are isomorphic.

Computers generally have little trouble determining if graphs are isomorphic. But for even the best algorithms, there is a worst-case scenario in which the solving time grows nearly exponentially as the number of nodes increases.

Babai claims that he has developed an algorithm that evaluates even the trickiest graphs in what’s called quasipolynomial time, which computer scientists consider reasonable. “We weren’t even close to quasipolynomial,” Williams says. The solving time still increases along with the number of nodes, but it does so much more gradually.

Babai declined an interview, saying he wants to confirm that his results survive several rounds of grilling from colleagues. It’s unusual for a mathematician to announce such a major result before submitting a written proof, says Neil Immerman, a theoretical computer scientist at the University of Massachusetts Amherst. But “Babai is very smart and reliable and one of the top world experts on the graph isomorphism problem,” Immerman says. “So I am sure that he has proved what he has announced.”

Jeremy Kun, a theoretical computer scientist at the University of Illinois at Chicago, warns that “it’s going to take a while for everyone to sort through the details.” But he came away impressed after attending the packed seminar. “Most of the proof seems like very, very hard work rather than a flash of insight,” he says.  

The advance could help researchers sort out a big mystery regarding whether every problem that can be easily verified can also be easily solved (SN Online: 9/9/10). Until Babai’s result, computers could quickly check if a solution showing that two graphs are isomorphic is correct, but they couldn’t necessarily solve the problem from scratch efficiently.

Some easily checkable problems are also quickly solvable; they belong to a category called P, for polynomial time. Others are classified as NP-complete (NP stands for nondeterministic polynomial time) and are the hardest to crack. The traveling salesman problem (SN Online: 2/20/12) is among the NP-complete puzzles. Graph isomorphism falls in between. Williams says that Babai’s discovery could improve understanding of the boundary zone between P and NP-complete, a region that includes problems such as factoring large integers, which is used for Internet security.