[Nauty] Isomorphism with coloured multigraphs

Paul T. Darga pdarga at umich.edu
Fri Apr 30 00:01:02 EST 2004


On Thu, Apr 29, 2004 at 02:36:51PM +0100, Chris Jefferson wrote:
> At first I tried to be clever and minimise my usage of colour
> until I discovered a) it makes things go slower

Here are my observations on this... there may of course be deeper
theoretical reasons that others may contribute.  :)

Symmetry detection, and particularly nauty's implementation, are very
sensitive to the number of vertices in the graph.  If you can find a
construction of your problem that minimizes the number of vertices, yet
still encodes all of the information about the problem (particularly,
which makes vertices maximally distinguishable), then nauty will be
much happier.

Coloring vertices is the best way to make such a thing happen.
While it might not be the most general theoretical approach, it is
in fact how nauty finds the automorphism group of a graph in the
first place.  Providing an initial vertex coloring helps nauty out a
great deal since it doesn't need to "discover" this initial coloring
on its own by wading through a sea of extraneous vertices.

Paul

-- 
Paul T. Darga - pdarga at umich.edu - http://www.eecs.umich.edu/~pdarga/
"When I gave food to the poor, they called me a saint. When I asked
why the poor were hungry, they called me a communist."
    -- Dom Helder Camara, Brazilian Bishop, Nobel Peace Prize nominee




More information about the Nauty mailing list