[Nauty] Schreir Sims Representation

[Brendan McKay]

* Bulutoglu Dursun A Civ AFIT/ENC <Dursun.Bulutoglu at afit.edu> [040721 23:48]:
> 	I was also wondering if there is a way I could get a set of
> strong generators from Nauty for a prespecified base. I understand this
> may be inefficient for longer bases but I need this for a specific
> application.

It is possible to control the base used by nauty according to its
combinatorial properties; for example, you could ensure that each element
in the base is adjacent to one of the provious elements.  However,
there is no way to specify an actual base.  The best option would be
to find the group and then do a change of base on it.  Probably the
"random Schreier" method would be best for this.  Presently I have no
software for this, but I should have.

>        One last thing. If I could get such a representation how
> inefficient would it be? If I choose all the nodes as my base how much
> longer would it take to compute the strong generators with respect to
> this base? Would the fastest algorithm for computing Schreir Sims
> Representation with respect to the base containing all the nodes take
> much longer than what nauty currently does?

If the base has vertices that are not really necessary, then there
are no generators (except the identity) at the levels corresponding to
those vertices.  It would not be a very serious inefficiency.

Changing the base using "random Schreier" would take more time than
nauty takes for easy graphs with large groups and less time for difficult
graphs.  So it depends on the application.

Brendan.