[Nauty-list] Hard Instances

[Gordon Royle]

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.

Gordon

--
Associate Professor Gordon Royle
Department of Computer Science & Software Engineering
University of Western Australia
http://people.csse.uwa.edu.au/gordon