What is graph canonisation?

Question

In a paper I am working on, I come across a term called "graph canonisation "

According to math-world Wolfram:

A canonical labeling, also called a canonical form, of a graph $G$ is a graph $G^{'}$ which is isomorphic to $G$ and which represents the whole isomorphism class of $G$ (Piperno 2011). The complexity class of canonical labeling is not known

Could one elaborate on that ?

Motivation : I am working on graph isomorphism (see Canonical labeling of graphs by L. Babai and E.M. Luks).

Answer 1

Daniel's answer is imperfect in two respects. First, it defines a perfect hash function for graphs taking values in an arbitrary set, but a "canonical form" usually means more than that in the literature. Second, it is not known to be NP-hard.

Let $\mathcal{G}$ be the set of labelled graphs (usually taken to be finite graphs but that probably doesn't matter). Suppose you can define a function $C:\mathcal{G}\to\mathcal{G}$ satisfying:

• For every $G\in\mathcal{G}$, $C(G)$ is isomorphic to $G$.
• For every isomorphic $G,H\in\mathcal{G}$, $C(G)=C(H)$.

(The last relation is identity not isomorphism.) Then $C(G)$ is called a canonical form of $G$.

One way to define a canonical form (but not the one used in the best algorithms) is to define a total order on labelled graphs then take $C(G)$ to be the least graph in the isomorphism class of $G$.

Answer 2

The wikipedia article seems to explain it pretty well: https://en.wikipedia.org/wiki/Graph_canonization

Answer 3

Essentially it's this. Let $\sigma : V \xrightarrow{\sim} V$ be the initial labeling of your vertices. Let $E$ represent your algorithm which is to return a canonical form $E(G) \in X$ some poset $(X,\leq)$ (usually a total ordering).

Then we say that $E(G)$ is a canonical form of $G$ if whenever $G \simeq H$ as graphs, we have that $E(G) = E(H)$ and conversely if $E(G) = E(H)$ then $G \simeq H$. So it is an injection from $\left(\textbf{YourGraphSpace}/{\simeq}\right)\rightarrowtail X$.

$X$ can be any set because we didn't refer to $\leq$ in the definition. However usually you have many $x \in X$ which correspond to the various labelings of $G$, and there could even be infinitely many! Usually in the optimization problem the least such $x \in X$ is designated as the standard form. I.e. $\operatorname{argmin}^{\leq}_{x \in X} (E(G) = x)$.

And doing so, finding the canonical form of any general class of graphs in a reasonable amount of running time is like any other NP-complete problem you'll find. It's extremely hard to solve.