Efficiently computing Orbital Graphs

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 closure⊕Other 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 G⊕Which 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

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 graphs⊕it 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