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$
$\endgroup$
2
-
$\begingroup$ What is a canonical form for a graph? $\endgroup$– Gerry MyersonJul 24, 2016 at 4:51
-
$\begingroup$ Gerry Myerson: I edited the question. By canonical form I meant canonical labeling of a graph. $\endgroup$– user95419Jul 24, 2016 at 15:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Jul 24, 2016 at 5:32