Graph Canonization - Computational Complexity

Computational Complexity

Clearly, the graph canonization problem is at least as computationally hard as the graph isomorphism problem. In fact, Graph Isomorphism is even AC0-reducible to Graph Canonization. However it is still an open question whether the two problems are polynomial time equivalent.

While existence of (deterministic) polynomial algorithms for Graph Isomorphism is still an open problem in the computational complexity theory, in 1977 Laszlo Babai reported that a simple vertex classification algorithm after only two refinement steps produces a canonical labeling of an n-vertex random graph with probability 1 − exp(−O(n)). Small modifications and added depth-first search step produce canonical labeling of all graphs in linear average time. This result sheds some light on the fact why many reported graph isomorphism algorithms behave well in practice. This was an important breakthrough in probabilistic complexity theory which became widely known in its manuscript form and which was still cited as an "unpublished manuscript" long after it was reported at a symposium.

The computation of the lexicographically smallest graph is NP-Hard.

For trees, a concise polynomial canonization algorithm requiring O(n) space is presented in. Begin by labeling each vertex with the string 01. Iteratively for each non-leaf x remove the leading 0 and trailing 1 from x's label; then sort x's label along with the labels of all adjacent leaves in lexicographic order. Concatenate these sorted labels, add back a leading 0 and trailing 1, make this the new label of x, and delete the adjacent leaves. If there are two vertices remaining, concatenate their labels in lexicographic order.