1
$\begingroup$

Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and attempt to further split the partition on more cells. What I found is that depending on the order of which you select cells during refinement, you can get different equitable partitions (at least up to the permutation of cells in the equitable partition). I guess this corresponds to the quote from Practical Graph Isomorphism II:

It is well known that for every colouring π there is a coarsest equitable colouring π' such that π' < π, and that π' is unique up to the order of its cells.

An example of this would be Example 7.7 (page 257), where selecting {1,3,7} instead of {2,4,5,6} will result in a permuted equitable partition

enter image description here

And more importantly these 2 equitable partitions can give 2 different certificates, so it is important to select the right order on the cells to get minimal among possible equitable partitions.

So my question is how does nauty ensure that during refinement it will find the “right” equitable partition and not lose the equitable partition that would potentially lead to the minimal certificate? In order words, among all (a) coarsest partitions how does it make sure to select the coarsest partition (because it selects just one equitable partition)?

$\endgroup$
1
$\begingroup$

After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected deterministically so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not necessarily give the certificate minimal among all possible discrete partitions, but rather minimal among some subset of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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