# How to find largest supergroup in polynomial time?

Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$: $$\pi : G \times [n]\mapsto [n]$$

In Input generating set of $G$ is given.

Question : I need to find the largest supergroup $G^{'}$ (generating set) of $G$ in $S_n$ which has same blocks as $G$.

For all $x \notin \langle G \rangle$

• check whether $\langle G,x\rangle$ has same blocks as $\langle G\rangle$
• If yes then add $x$ to the generating set of $G$
• Else do nothing

This is a brute force algorithm and running time of this algorithm is exponential many operations i.e. $O(n^n)$.

Question : Is there an polynomial time algorithm for the above problem ?

Motivation : Isomorphism of hyper-graphs of low rank in moderately exponential time (see this)

• Why the hyperlink from supergroup? That seems to reduce the clarity of the question, not enhance it. – Peter Taylor Aug 22 '17 at 10:14
• @ Peter Taylor I Have edited the question – adc Aug 22 '17 at 10:19
• Is $G'$ the commutator subgroup of $G$, or a typo? – Emil Jeřábek Aug 22 '17 at 14:08
• @ Emil Jeřábek No $G^{'}$ is not the commutator subgroup of $G$ – adc Aug 22 '17 at 14:12
• What is it, then? – Emil Jeřábek Aug 22 '17 at 14:38

Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$).
First, it's easy to reduce to the case of transitive $G$.
Next, find the minimal blocks of $G$. (See e.g. Section 3.6(B) of Dixon & Mortimer.) This can be done by choosing a point $x \in [n]$, and for each $y \in [n]$, $y \neq x$, computing the (undirected) connected components of the orbital digraph generated by $(x,y)$. Each such connected component is a block; take the smallest ones.
If there are $b$ blocks each of size $s$, then the desired group is the wreath product $S_b \wr S_s = (S_b)^s \rtimes S_s$ in its natural action on $[n]$.