László Pyber:
Babai’s fast algorithm for the graph isomorphism
problem
Graph isomorphism in quasipolynomial time.
Let us be given two graphs G1, G2 of
n vertices. Are they isomorphic? Giving an always efficient
algorithm to answer this question remained an open problem for a long
time. In 2015 Babai showed how to solve this problem – and
others linked to this – in quasi-polynomial time, i.e. in time
exp ((log n)const). His strategy is based in part on the
algorithm by Luks (1980/82), who solved the case of graphs of bounded
degree in polynomial time. Both algorithms use a considerable amount
of finite group theory. Indeed, the original algorithm of Babai relies
on the Classification of Finite Simple Groups (CFSG).
The speaker showed in 2016 how to change a small but important part of Babai’s argument to replace the use of CFSG by an elementary permutation group theoretic argument and obtain a weaker, but still quasipolynomial bound on the running time of the algorithm.