36.7. Performance🔗

The six-way comparison runs C dense nauty, C sparse nauty, C Traces, Hex dense, Hex sparse and Alex Meiburg's IsoGraph on the same 333 labelled graphs from 20 families, through 3,072 vertices. It measures native canonicalization after input construction. For Hex sparse this includes parsing the returned label and producing normalized sparse canonical rows. It does not include certificate production or kernel replay.

Open the family plot or cactus plot at full size to inspect the individual curves.

In the retained measurements, the implementations complete these numbers of instances within the five-second per-call cutoff:

On 282 cases completed by both Hex implementations, the median per-instance sparse/dense time ratio is 0.25. On 296 cases completed by both Hex sparse and IsoGraph, the corresponding ratio is 0.73. These ratios describe different solved subsets. The sparse measurements were refreshed while the other five series were retained from earlier sessions on the same shared host, so the ratios are observations about this corpus, not universal speed factors.

The family plot shows where each algorithm does well. A cross marks where a series stops: a call exceeding five seconds stops that series on the family, and larger sizes are not attempted. Missing observations are not assigned the cutoff time. The cactus plot sorts each series' completed instances independently; farther right means more completed instances, while lower means less time. Neither plot claims a general complexity bound for graph isomorphism.

The protocol uses two passes, a warmup and five timed calls per case (one when warmup exceeds one second), and reports the minimum completed call. The comparison report records the corpus, versions, input boundaries, stopping rules, raw outcomes and reproduction commands. Its search and conversion figure and tables separate construction and relabelling costs. Constructing a sparse graph from edges avoids a dense intermediate; converting an existing matrix still requires reading that matrix.

Conformance compares Hex dense with C dense, and Hex sparse with C sparse. The sparse comparison agrees on visited-node counts on every completed case. Its per-node scaling check passes the recorded 0.2 exponent tolerance on every family with enough matched sizes. This is evidence that the representation improvements preserve the intended search, rather than evidence that dense, sparse and Traces explore the same tree.

Proof-producing use has separate costs. A call to graph_iso must construct a proof whose decisive checks run in the kernel. Positive transporter checks and negative certificate replays can have very different costs, and neither can be inferred from native canonicalization timings. The validation report links the separate automorphism, certificate-production, native-replay and imported kernel-proof measurements. The public totality and correctness theorems apply to the optimized sparse search used in the comparison.