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)
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 &amp; 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]$.