The Complexity of McKay's Canonical Labeling Algorithm (1995)

---

Link: https://doi.org/10.1090/dimacs/028/14

Abstract: We study the time complexity of McKay’s algorithm to compute canonical forms and automorphism groups of graphs. The algorithm is based on a type of backtrack search, and it performs pruning by discovered auto-morphisms and by hashing partial information of vertex labelings. In practice, the algorithm is implemented in the nauty package. We obtain colorings of Fürer’s graphs that allow the algorithm to compute their canonical forms in polynomial time. We then prove an exponential lower bound of the algorithm for connected 3-regular graphs of color-class size 4 using Fürer’s construction. We conducted experiments with nauty for these graphs. Our experimental results also indicate the same exponential lower bound.

---