Faster Canonical Forms for Strongly Regular Graphs

We show that a canonical form for strongly regular (s. r.) graphs can be found in time exp(Õ(n^1/5))and therefore isomorphism of s. r. graphs can be tested within the same time bound, where n is the number of vertices and the tilde hides a polylogarithmic factor. The best previous bound for testing isomorphism of s. r. graphs was exp(Õ(n^1/3)) (Spielman, STOC 1996) while the bound for GI in general has been standing lirmly at exp(Õ(n^1/2)) for three decades. (These results, too, provided canonical forms.) The previous bounds on isomorphism of s. r. graphs (Babai 1980 and Spielman 1996) were based on the analysis of the classical individualization/relinement (I/R) heuristic. The present bound depends on a combination of a deeper analysis of the I/R heuristic with Luks´s group theoretic divide-and-conquer methods following BabaiLuks (STOC 1983) and Miller (1983). Our analysis builds on Spielman´s work that brought Neumaier´s 1979 classilication of s. r. graphs to bear on the problem. One of Neumaier´s classes, the line-graphs of Steiner 2-designs, has been eliminated as a bottleneck in recent work by the present authors (STOC´13). In the remaining hard cases, we have the benelit of “Neumaier´s claw bound” and its asymptotic consequences derived by Spielman, some of which we improve via a new “clique geometry.” We also prove, by an analysis of the I/R heuristic, that, with known (trivial) exceptions, s. r. graphs have exp(Õ(n^9/37)) automorphisms, improving Spielman´s exp(Õ(n^1/3)) bound. No knowledge of group theory is required for this paper. The group theoretic method is only used through an easily stated combinatorial consequence (Babai-Luks, 1983 combined with Miller, 1983). While the bulk of this paper is joint work by the live authors, it also includes two contributions by subsets of the authors: the clique geometry [BW] and the - utomorphism bound [CST].