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)

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

1 Answer 1


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]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.