[Nauty] Complexity

[Brendan McKay]

* Wahid Chrabakh <chrabakh at cs.ucsb.edu> [040308 15:23]:
> Hi:
> 	What is the difference in complexity theorretically or imperically
> between finding the canonical form or a graph or finding the
> automorphism group of the same graph using nauty?

Empirically there is hardly any difference for moderately difficult
graphs but for very easy graphs such as random graphs the group is
almost always trivial and finding the canonical labelling takes
about 10 times as long.

Theoretically, nobody has any idea!

Brendan.