New algorithm for comparing graphs may be breakthrough in complexity theory

Science : The graph isomorphism problem poses the challenge of determining whether two graphs—networks of interconnected nodes, which can be drawn in multiple ways—are the same. The previous best method, developed by Eugene Luks in 1983, is an algorithm in which the number of steps necessary for the comparison increases exponentially as the number of nodes, n, in the graphs increases—what is referred to as exponential time. Now László Babai of the University of Chicago has developed an algorithm that appears to achieve the same task in polynomial time—the number of steps grows at a rate more like n² than 2ⁿ. Current computers are more than capable of solving most graph isomorphism problems quickly, but the development of the new algorithm shows that more complicated problems are not necessarily unsolvable in a reasonable amount of time.