Efficiently computing Orbital Graphs

by Markus Pfeiffer

Finishing some long overdue work, I was recently benchmarking different ways to compute orbital closures of permutation groups.

Or­bital Clo­sures, and what oth­ers call them

Lets first lay down what I am computing.

Suppose that (as per usual) \Omega = \{1..n\} for some n \in \mathbb{N} and G \leq S_{\Omega}. If we pick two distinct numbers \alpha, \beta \in \Omega, then the graph \Gamma_{(\alpha,\beta)} = \left<\Omega, \left(\alpha, \beta\right)^G\right> is the orbital graph of G with base pair (\alpha, \beta).

If we now take all orbital graphs of G by considering all possible base pairs and intersect their automorphism groups, we get the orbital closureOther authors call this construction the 2-closure of G, or talk about the automorphism group of an association scheme.

\mathcal{OC}(G) = \bigcap\limits_{(\alpha,\beta) \in \Omega^2} \operatorname{Aut}(\Gamma_{(\alpha,\beta)})

of GWhich necessarily contains G, but might be bigger.

Naive com­pu­ta­tions

In GAP we could naively compute the group \mathcal{OC}\left(G\right) as follows

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Or­bital­Graphs := func­tion(G)
  lo­cal base­pairs;

  base­pairs := Arrange­ments([1..Largest­Moved­Point(G)], 2);

  re­turn List(base­pairs, bp -> Di­graph­By­Edges(Or­bit(G, bp, On­Tu­ples)));
end;

og := Or­bital­Graphs(G);
ogauts := List(og, Au­to­mor­phism­Group);
oc := In­ter­sec­tion(ogauts)

The code above is already unbearably slow for fairly small examples. Our method for computing orbital graphs is not very efficient. In a separate post I describe how we use some basic group theory to make the computation of orbital graphs a lot faster by not computing many graphs that turn out to be isomorphic to a graph that we already computed.

Once we use the more efficient way of computing orbital graphs, and if we happen to use groups with very few distinct orbital graphsit is clear from the algorithm described in ... which type of group that is, we get away with this approach for quite some time.

Trying to compute the orbital closure of G = D_{32} \wr D_{32} makes the wait already quite painful.

Exploring what takes so long in this computation yields some insight: We compute the automorphism group of each orbital graph separately, intersecting the results. Group intersection is a hard problem, though it is no harder than graph automorphism finding.

Clev­er­er con­struc­tion

A slightly cleverer way of computing the orbital closure is not to compute a truckload of graphs, their automorphism groups, and intersecting them, but to just compute one graph with coloured edges, and handing that to a graph automorphism solver. This should of course yield the same result, but using a very efficient graph automorphism finder works a lot better.thanks go to Finn Smith for adding code to the GAP package digraphs to compute automorphisms of edge-coloured digraphs

Bench­marks in GAP with Di­graphs and fer­ret

Putting this together I did some benchmark comparisons using GAP 4.11, digraphs, and ferret and found that the edge-coloured method is up to a factor of 1000 faster. Hence the new default method in the orbitalgraphs package is using the edge-coloured graph method as a default.

So­phis­ti­cat­ed Al­go­rithms

Write something about Johannes Hahn’s algorithm