[Nauty] A decreasing runtime with an increasing number of edges of an isomorphism test

[Brendan McKay]

* Kukluk, Jacek P <kukluk at uta.edu> [050213 05:20]:
> We studied an isomorphism test of planar graphs. Our paper was accepted
> in JGAA and we are working on some revisions.  We used Nauty as a
> reference in comparing performance. We observed that Nauty's runtime
> decreases with increasing number of edges. We would like to understand
> why. 
>  
> More specifically, in one of our experiments, we generate one thousand
> planar graphs with number of vertices |V|=80. We repeated two times this
> experiment with isomorphic and nonisomorphic graphs. As we increase
> number of edges from |V|-1 to 3|V|-6 we observe decreasing running time.
> We did this experiment with other number of vertices with the same
> result. How to explain this phenomenon which appears to be
> counter-intuitive?

There are two reasons which probably both play a part.

1. At the lower end of the range there are many automorphisms but at
the the upper end there are few. A major component of nauty's time
is the computation of the automorphism group, so that component
will decrease with increasing numbers of edges.

2. Some of the key components of nauty are tuned for dense graphs
and are sub-optimal for sparse graphs. This is true both for the
data structures and the algorithms employed. There are very few
places in nauty where individual edges are looked at, so nothing is
gained if there are fewer edges. On the contrary, increasing the
density might increase the efficiency.

The next major release of nauty will not have property 2.  I have
a prototype running and sometimes the improvement is spectacular.

Brendan.