[Nauty-list] genrang -r8 problem

[Gordon Royle]

On 29/08/2007, at 9:02 PM, Brendan McKay wrote:

> It will terminate after a few days. The algorithm used for order n
> and degree r takes time proportional to n*exp(r^2/4) for fixed r and
> large n. For small n and large r, the time is worse.
>
> You can generate the complement instead if it has lower degree.
> Otherwise you don't have an option except to implement a better
> algorithm.
>
> Brendan.

If I recall correctly, the existing algorithm works by finding a  
random perfect matching in graph with n groups of r vertices and then  
squishing each group down to a single vertex thus creating a  
multigraph with loops. So the limiting factor is the proportion of  
these multigraphs with loops that happen to be simple - is that right?

Presumably it would be feasible to do a Markov chain type algorithm  
based on doing "Ryser switches" on pairs of edges (using the fact  
that any two graphs of the same degree sequence are related by a  
sequence of such switches)... but presumably determining the mixing  
time of such a Markov chain is impossibly difficult and hence we  
would never know how long to run it before taking a sample...

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