[Nauty-list] Hard Instances
gordon at csse.uwa.edu.au
Sun Mar 25 21:27:59 EST 2007
On 21/03/2007, at 12:18 PM, Greg Tener wrote:
> I have three questions about hard instances for nauty (they're so
> few and hard to find).
My past experience is that projective planes are the only
pathologically difficult cases for nauty.
Of course Brendan has since added invariants specifically based on
that observation, and so they are now much more doable than
previously. But they are still massively more difficult than any
other graphs of similar size / regularity etc.
Again based on my empirical and informal observations, it is true
that Latin square graphs seem to be harder than regular graphs of
similar size, but to nothing like the same extent as projective planes.
If you are interested in some more projective planes, then I have a
list of 1349 projective planes of order 49 (they have 2451 points and
2451 lines so that is a 4902 vertex graph). They are all translation
planes so they have at least a biggish automorphism group. I think
that nauty would find them very hard indeed.
Associate Professor Gordon Royle
Department of Computer Science & Software Engineering
University of Western Australia
More information about the Nauty