Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)

Abstract

Soient donnés deux graphes ${\Gamma }_1$, ${\Gamma }_2$ à $n$ sommets. Sont-ils isomorphes? S'ils le sont, l'ensemble des isomorphismes de ${\Gamma }_1$ à ${\Gamma }_2$ peut être identifié avec une classe $H\pi$ du groupe symétrique sur $n$ éléments. Comment trouver $\pi$ et des générateurs de $H$? Le défi de donner un algorithme toujours efficace en réponse à ces questions est resté longtemps ouvert. Babai a récemment montré comment résoudre ces questions -- et d'autres qui y sont liées -- en temps quasi-polynomial, c'est-à-dire en temps $\exp (O(\log n{)}^{O(1)})$. Sa stratégie est basée en partie sur l'algorithme de Luks (1980/82), qui a résolu le cas de graphes de degré borné. English translation: Graph isomorphisms in quasipolynomial time [after Babai and Luks, Weisfeiler--Leman,...]. Let ${\Gamma }_1$, ${\Gamma }_2$ be two graphs with $n$ vertices. Are they isomorphic? If any isomorphisms from ${\Gamma }_1$ to ${\Gamma }_2$ exist, they form a coset $H\pi$ in the symmetric group on $n$ elements. How can we find a representative $\pi$ and a set of generators for $H$? Finding an algorithm that answers such questions efficiently (in all cases) is a challenge that has long remained open. Babai has recently shown how to solve these problems and related ones in quasipolynomial time, i.e., time $\exp (O(\log n{)}^{O(1)})$. His strategy is based in part on an algorithm due to Luks (1980/82), who solved the case of graphs of bounded degree.

Expository paper associated to Bourbaki seminar (Jan 14, 2017). 43 pages, in French. To appear in Astérisque. Fascicule no 1125 of the Bourbaki seminar (69th year, 2016-2017)

Cited by in corpus (2)

• A CFSG-free analysis of Babai's quasipolynomial GI-algorithm
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs