A non-factorial algorithm for canonical numbering of a graph

Reviewer: J. C. Lagarias

Let K be a class of labeled graphs with the vertex set {1,2,. . ., n- } that is closed under isomorphism. The problem of canonical numbering (or canonical labeling) of the graphs in K is to pick one member out of each isomorphism class of graphs in K; that is, to find a function CF: K:2WZK, such that CF( G:) :9V G and G 1 :9V G 2 implies CF( G 1) = CF( G 2). For any definition of canonical labeling, there is an associated canonical form algorithm problem: Given G, compute CF( G); that is, find that permutation of the vertices of G that is CF( G). Any algorithm to compute a canonical form can be used to test graph isomorphism; however, the graph isomorphism problem may be easier than finding canonical labelings. There has been a lot of research lately on finding canonical labelings. The simplest types of canonical labeling are to choose CF( G) to be that labeled graph G* :9V G whose incidence matrix is smallest in some lexicographic ordering of incidence matrices. It has been shown that computing one such type of canonical labeling is NP-hard. The trivial algorithm for finding a canonical labeling checks all n] isomorphic graphs. Recent research has concentrated on finding more complicated canonical labelings which can be computed more quickly. Typically, the canonical labelings so obtained are defined in terms of the algorithm for finding them and have no simple direct definition. The paper under review gives such an algorithmic definition of a canonical labeling CF* for all graphs on n vertices and an algorithm for finding CF*( G) given G in 0( c n) time. The algorithm for computing CF*( G) is combinatorial in nature, and uses no explicit group theory. It uses ideas of refinement to a stable partition of vertices and a notion called sectioning introduced by Goldberg [1]. This algorithm was the first canonical labeling algorithm asymptotically faster than n] to be found. Babai and Luks [2] have subsequently found a canonical labeling function CF** based on group theoretic ideas, and an algorithm using group theory for computing their canonical labeling in 0(exp ( n 1/2 + 0(1)) time.