A practical graph isomorphism solver and an explicit quasi-polynomial bound

We give two results, and keep apart what is proved, measured and conjectured.Proved: for a quasi-polynomial isomorphism algorithm that uses Babai’s giant caseas its last fallback, we make the leading branching constants explicit: countinglog2 of the number of branches (“bits”), String Isomorphism of length N costs atmost 11.4 (log2 N )^3 (1 + o(1)) bits, about 4.3 times below Dona’s explicit bound(49.4 (log2 N )^3 in the same units), and Graph Isomorphism on v vertices at most43.4 (log2 v)^3 (1 + o(1)) bits (5.4 (log2 |Ω|)^3 in string units, |Ω| ≈ v 2 ). The exponent3 is that of Helfgott, Bajpai and Dona and is not improved; the polynomial workper branch is not made numeric. Measured: the implemented solver (refinement, arooted decomposition with recursion inside its pieces, linear algebra over abeliangroups and Luks’ method for bounded groups) computes the automorphism group,and decides isomorphism through the disjoint union, on all 12,001 instances of 36benchmark families and on every hard diagnostic instance we constructed; it neverreturns a wrong answer, and its giant-case fallback is specified but not implementedbecause no instance reached it. Conditional and conjectured: under an explicithypothesis (DG ) on the algorithm’s branches the giant case is not needed and thegraph bound is 6.84 (log2 v)^3 bits; we conjecture that every graph satisfies (DG ) andreport the evidence.