1
$\begingroup$

I have consulted the literature concerning graph isomorphism algorithms, and all papers I could find involve finding a canonical representation of a graph. So to decide whether two graphs are isomorphic, you just check if they have the same canonical representation (i.e. the same equivalence class).

There is, also, an other way to proceed: try to build explicitly the isomorphism between the two graphs, and answer Yes or No depending on the success of the task. One can think, for instance, to a constructive algorithm that incrementally build a bijection, using backtracking.

I was not able to find any literature related to the second topic. I understand that canonical representation is a better idea in general, but I am quite surprised that nobody ever tried to tackle the constructive approach. Maybe it is too naive ? My question is: do you know any literature on that topic, that I could have missed ?

$\endgroup$

1 Answer 1

1
$\begingroup$

A canonical labeling of a graph is a labeling of the nodes. One can construct the isomorphism mapping by tracking how the nodes are labeled when computing the canonical form, and undoing the mapping with the two graphs. In particular, the labeling is usually a coloring where each node of a given color is connected to the same quantity of nodes of the same set of colors.

A symmetric coloring of a graph on 9 nodes.

Given that two nodes in either graph map to the same color, then those nodes can safely be mapped to each other. Considerable detail on how these colorings are generated is provided in McKay & Piperno, Practical graph isomorphism, II, 2014. This coloring is also the approach taken in the relatively recent breakthrough in Babai, Graph isomorphism in quasipolynomial time, 2016.

That said, there are some algorithms that build mappings directly. A common algorithm in practice is the VF2 algorithm by Cordolla et al., An improved algorithm for matching large graphs, 2001 which computes a mapping recursively.

$\endgroup$
1
  • $\begingroup$ Thank you, I knew about the first two (and the labelling is typically what I understood as the canonical representation methods, so thank you for the remainder) but not about the third one, I will look at it. $\endgroup$ Oct 12, 2022 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.