The graph isomorphism problem can be solved in quasipolynomial time

You need to know: Graph, finite graph, isomophic graphs, algoruthm, running time of an algorithm, big O notation.

Background: The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

The Theorem: On 11th December 2015, László Babai submitted to arxiv a paper in which he proved the existence of an algorithm for the graph isomorphism problem for n-vertex graphs with running time for some fixed .

Short context: The graph isomorphism problem is one of the fundamental problems in the theory of algorithms on graphs. The isomorphism problems for many other objects, such as groups, can be reduced to it. It has been intensively studied for decades, and efficient algorithms for many families of graphs are known. However, despite substantial efforts, the time algorithm discovered by Babai and Luks in 1983 remained the fastest one working for all n-vertex graphs. The Theorem provides a much faster algorithm. Algorithms with running time are called quasipolynomial time algorithms.

Links: Free arxiv version of the original paper is here.

Go to the list of all theorems