Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract

Primitive coherent configurations (PCCs) are edge-colored digraphs that generalize strongly regular graphs (SRGs), a class perceived as difficult for Graph Isomorphism (GI). Moreover, PCCs arise naturally as obstacles to combinatorial divide-and-conquer approaches for general GI. In a natural sense, the isomorphism problem for PCCs is a stepping stone between SRGs and general GI. In his 1981 paper in the Annals of Math., Babai proposed a combinatorial approach to GI testing via an analysis of the standard individualization/refinement (I/R) technique and proved that I/R yields canonical forms of PCCs in time exp(~O(n 1/2 )). (The tilde hides polylogarithmic factors.) We improve this bound to exp(~O(n 1/3 )). This is faster than the current best bound, exp(~O(n 1/2 )), for general GI, and subsumes Spielman's exp(~O(n 1/3 )) bound for SRGs (STOC'96, only recently improved to exp(~O(n 1/5 )) by the present authors and their coauthors (FOCS'13)).

Authors

• Xiaorui Sun
• John Wilmes

Keywords

• graph isomorphism
• primitive coherent configurations
• algorithms
• association schemes
• complexity
• strongly regular graphs