[Nauty] Hard Graphs?

[Mark Goldberg]

The currently fastest (asymptotically) algorithm for constructing a
canonical vertex numbering of a graph, due to Babai and Luks, runs
in O(exp(n^{1/2 +o(1)}) time.

On the other hand, the canonical numbering of bipartite graphs of 
the projective planes is achieved in the time O(n^{log log n}).
The algorithm due to Gary Miller is based on a well known(?) theorem
by Brock (I am not sure about the name, but hopefully somebody will 
correct me). The theorem says :
	Let P and Q be two projective planes, where P is a subset of Q,
	and let x be an element of Q-P. Then the size of the smallest
	projective subplane of Q containing P and x is at least |Q|^2
	/*sorry, at the moment I don't have any book on projective
	planes with me and cannot recall the exact formulation of the
	bound; the point is that the size is growing quadratically
	when we add an element, which implies that only loglogn steps
	are needed to obtain Q from P*/

I don't see this as a contradiction to your experimental evidence.
Probably, nobody thinks that the Babai&Luks algorithm reflects the 
complexity of ISO.
I believe for a long time that there should be an algorithm which 
contsructs a canonical numbering  of an arbitrary graph in 
O(n^{log log n}) time.

Thus, your observation that the projective planes are the hardest
graphs  for ISO is correct in my view.

-Mark

>Gordon writes:
>
>> Mark writes:
>
> > It's interesting though, that the bipartite graphs of projective planes
> > are identified in O(n^{log log n}) time. This is by far fastewr then the
> > currently fastest general canonical numbering algorithm.
>
> Sorry, but I am not sure what you mean by this... can you please elaborate?
>
> When you say "identified", do you mean "recognized as the graph of a
> projective plane" or "recognized as the graph of a *specific* projective
> plane"?
>
> Thanks
>
> gordon
>
>
>
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list