Counting the work of a stabiliser chain for graph isomorphism: a tighter cost bound, a polynomial-time condition, and measurements

A stabiliser chain computes the automorphism group of a graph. It fixes a few vertices (roots), computes the symmetriesthat fix them by linear algebra, and decides the images of each root by a search pruned by invariants (the tuplesearch). In earlier work the chain was the front end of a quasi-polynomial algorithm, which received every question thechain left open. We show that this fallback is not needed. With a fixed work budget per linear-algebra solve, the chainfixes one more root instead and always ends with the exact group. This assumes canonical colour names without hashcollisions and a metering property of the code. One invocation costs poly(n)·(1+τ), where τ is the number of nodes of the largest tuple search. Only τ is not bounded bya fixed polynomial. So the budgeted chain is polynomial on a family of graphs if and only if τ ≤ n^t on the family forone constant t, a condition we call G2+. On such a family, automorphism groups are computed in polynomial time, and so isisomorphism if the family contains the disjoint unions that the test runs on. G2+ holds on every family with a boundednumber of roots, and on every family where every dead branch ends within t steps. It is a condition, not a conjecture;the conjecture of this programme remains the quasi-polynomial G2 of the earlier work. We measure τ on families chosen to be hard for the chain. On five families (539 instances, n ≤ 1,514) every run is exactand τ ≤ n^0.70. On Latin square graphs of random p-groups of class 2 (17 instances, up to 65,536 vertices), τ ≤ N^0.69;these data do not settle how fast τ grows. An appendix gives an exact quadrangle census of the 243 projective planes oforder at most 27 in our benchmark, checked against Killgrove's counts, and a reduction of Killgrove's conjecture. Code, result files and scripts: https://github.com/ckaratzas/dialysis-aut (main branch).