Complexity
Babai's algorithm: O(exp(polylog(n))). Massive breakthrough over previous exp(√(n log n)).
Advertisement
Nauty / Bliss
Practical implementations. Canonical form via node-refinement + backtracking. Handle graphs with 10⁵ nodes.
Advertisement
Special cases
Trees: O(V) via canonical form. Planar: O(V) via Hopcroft-Wong. Bounded genus: polynomial.
Weisfeiler-Leman
Iterative color refinement. k-WL captures all graphs up to k-th order equivalence. Foundation of GNN expressiveness theory.