Graph canonization

Graph canonization is finding a canonical form of a graph G, which is a graph Canon(G) isomorphic to G such that Canon(H)=Canon(G) if and only if H is isomorphic to G. The canonical form of a graph is an example of a compete graph invariant. Since the vertex sets of (finite) graphs are commonly identified with the intervals of integers 1,..., n, where n is the number of the vertices of a graph, a canonical form of a graph is commonly called canonical labeling of a graph.

A commonly known canonical form is the lexicographically smallest graph within the isomorphism class, which is the graph of the class with lexicographically smallest adjacency matrix considered as a linear string.

Computational complexity

Clearly, the graph canonization problem is at least as computationally hard as the graph isomorphism problem. In fact, Graph Isomorphism is evenAC⁰-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 2 refinement steps produces a canonical labeling of an n-vertex random graph with probability 1-exp(O(n)). It shed 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-complete.

Applications

Graph canonization is the essence of many graph isomorphism algorithms.

A common application of graph canonization is in graphical data mining, in particular in chemical database applications.

A number of identifiers for chemical substances, such as SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information and to facilitate the search for such information in databases and on the web, use canonization step in their computation, which is essentially the canonization of the graph which represents the molecule.