Suppose we know the orbit partition of the vertices of a graph (due to the action of its automorphism group). Is it easy (as in "polynomial time") to generate a canonical form (aka "canonical labeling") for that graph using its orbit partition? A quick Google search did not reveal any material that looked like it contains an answer. Wikipedia was not helpful either.
I found some interesting work done by McKay and Piperno using "equitable" partitions (I'm currently reading Practical Graph Isomorphism II), but so far that appears mostly heuristic over a potentially large search space and may be I'm too dumb to make a connection to orbit partitions. (I know that every orbit partition is equitable but the reverse in general is not true.)

  • $\begingroup$ What is a canonical form for a graph? $\endgroup$ – Gerry Myerson Jul 24 '16 at 4:51
  • $\begingroup$ Gerry Myerson: I edited the question. By canonical form I meant canonical labeling of a graph. $\endgroup$ – J Reed Jul 24 '16 at 15:53

The answer is "no", but only because nobody knows how quickly graph isomorphism and canonical labelling can be done. There is no theory to suggest that knowing the orbits will help much, although it might allow some useful heuristics in practice. Consider the case that the group is trivial: knowing that in advance is hardly any information at all, since most graphs have trivial groups.


protected by Community Jul 24 '16 at 17:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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