In graph theory, a branch of mathematics, graph canonization is the problem finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.
Contents
The canonical form of a graph is an example of a complete graph invariant: every two isomorphic graphs have the same canonical form, and every two non-isomorphic graphs have different canonical forms. Conversely, every complete invariant of graphs may be used to construct a canonical form. The vertex set of an n-vertex graph may be identified with the integers from 1 to n, and using such an identification a canonical form of a graph may also be described as a permutation of its vertices. Canonical forms of a graph are also called canonical labelings, and graph canonization is also sometimes known as graph canonicalization.
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 with probability at least 1 − exp(−O(n)), a simple vertex classification algorithm after only two refinement steps produces a canonical labeling of a graph chosen uniformly at random from the set of all n-vertex graphs. Small modifications and an added depth-first search step produce canonical labeling of such uniformly-chosen random graphs in linear expected 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.
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. However, the computation of the lexicographically smallest graph is NP-hard.
For trees, a concise polynomial canonization algorithm requiring O(n) space is presented by Read (1972). 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.
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 use canonicalization steps in their computation, which is essentially the canonicalization of the graph which represents the molecule. These identifiers are designed to provide a standard (and sometimes human-readable) way to encode molecular information and to facilitate the search for such information in databases and on the web.