A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen, Pascal Schweitzer · 2018
In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^O((log d)^c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d log d).