New Algorithm Cracks Graph Problem

by  Andrew Grant,  ScienceNews

The graph isomorphism problem can now be efficiently solved thanks to a new algorithm devised by computer scientist Laszlo Babai, who unveiled the algorithm Tuesday at a University of Chicago seminar.

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.

Babai says his breakthrough eliminates the possibility that extremely complex graphs would make a solution to the problem impossible. He says the algorithm assesses the most complicated graphs in quasipolynomial time, in which the solving time increases along with the number of graph nodes, but at a more gradual pace.

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.

Stanford University researcher Ryan Williams thinks Babai’s milestone may be the most significant theoretical computer science advance in more than 10 years. It could help scientists address the mystery of whether every problem that can be easily confirmed can be easily solved.

Williams says Babai’s work could improve the understanding of the border between polynomial time and nondeterministic polynomial time-complete problems.

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.  Read the report.