Fast algorithm for graph isomorphism problem published

These two graphs are isomorphic

Mathematician Laszlo Babai (László Babai) from the Faculty of Computer Science and Mathematics of the University of Chicago presented a fast new algorithm for solving the problem of graph isomorphism, one of the fundamental problems of the theory of computational complexity. The algorithm brings the problem very close to class P. According to some experts, this is one of the most significant results in theoretical computer science in a decade, if not in several decades.

The creation of the algorithm Laszlo announced a month ago. According to him, the algorithm is much more efficient than the best of the existing ones , which was the record holder for more than thirty years: it was developed by Professor Eugene Lux in 1983, who solved the problem in subexponential time.

Apparently, Laszlo Babay managed to practically reduce the problem to the task of class P: its algorithm is declared as calculated in quasi-polynomial time.
')
On December 11, 2015, an article describing the new algorithm was finally published in open access, and also sent to the Association for Computing Machinery. The official presentation of the algorithm will be held at the 48th Symposium on Computation Theory .

For several decades, the problem of graph isomorphism had a special status in the theory of computational complexity. While hundreds of other tasks humbly succumbed to classification by class P or class NP, the problem of graph isomorphism could not be unambiguously categorized. It seemed harder than light tasks and easier than complex ones, occupying a unique position as if between two classes of tasks. This is one of two famous tasks in this strange intermediate area, says Scott Aaronson, a mathematician at the Massachusetts Institute of Technology. Now, in his words, “it looks like one of the two gave up.”

The second well-known problem from the "gray" area - factorization of integers.

The graph isomorphism problem itself looks simple: you need to determine whether two graphs are isomorphic, that is, whether it is possible to transform one graph into another simply by moving the vertices, while maintaining the connections between the vertices. That's all. Despite the seeming simplicity, this task is difficult to solve, because even small graphs can take many different forms.


Laszlo Babai presents his algorithm for solving the problem of graph isomorphism on November 10, 2015 at the University of Chicago

The Laszlo Babai algorithm works by virtual “coloring” of graph vertices. First, several vertices are randomly selected, they are “painted” in different colors. Then several vertices are selected in the second graph, presumably corresponding to the vertices from the first graph, they are assigned the same colors. In the end, all options are sorted out. After the initial selection, the algorithm paints on both graphs supposedly isomorphic vertices adjacent to the initially selected ones, in different colors until there are no connections between the vertices.

If Babay’s algorithm is tested by colleagues, this is the most significant discovery in this section of mathematics lately. “Before his announcement, hardly anyone except, perhaps, himself, assumed the appearance of such a result in the next ten years, if ever, at all,” said Joshua Grochow of the Santa Fe Institute.

Over the past few weeks, Babay has given several lectures outlining his algorithm. A video of the first lecture of November 10 is presented below.



The problem of isomorphism of graphs is considered “universal”, that is, any problem can be reduced to it, where the question of isomorphism of combinatorial structures is raised. Typically, this "universality" is characteristic of tasks of the class NP. At the same time, the problem of graph isomorphism demonstrated one strange property that no NP-complete problem has: passing the “blind test” ( Arthur-Merlin protocol ).

In 2012, an informal survey of scientists in the field of theoretical informatics gave the following result: 14 of them expressed that the problem of graph isomorphism belongs to the class P, and six said they did not belong. Before the announcement of Laszlo Babaya, few thought that the task would be solved sometime in the near future. “I thought that maybe she belongs to the P class, but maybe not, but during my life no one will know,” admitted Grochou.

Laszlo Babai worked on the problem of graph isomorphism for almost 40 years.