<p>Yes, this can be solved in polynomial time (and, I think, even in $\mathsf{NC}$).</p>

<p>First, it's easy to reduce to the case of transitive $G$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-08-22T22:23:17.080Z
2017-08-22T22:23:17.080Z
Joshua Grochow
<p>Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$: 
$$\pi : G \times [n]\mapsto [n] $$ </p>

<p>In Input generating set of $G$ is given. </p>

<p><strong>Question :</strong> I need to find the largest supergroup $G^{'}$ (generating set) of $G$  in $S_n$ which has same <a href="https://en.wikipedia.org/wiki/Block_(permutation_group_theory)" rel="noreferrer">blocks</a> as $G$.</p>

<blockquote>
  <p>For all $x \notin \langle G \rangle$</p>
  
  <ul>
  <li>check whether $\langle G,x\rangle$ has same blocks as $\langle G\rangle$
  
  <ul>
  <li>If yes then add $x$ to the generating set of $G$</li>
  <li>Else do nothing</li>
  </ul></li>
  </ul>
</blockquote>

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

<p><strong>Question  :</strong> Is there an polynomial time algorithm for the above problem ?</p>

<p><strong>Motivation :</strong> Isomorphism of hyper-graphs of low rank in moderately exponential time <a href="https://people.cs.uchicago.edu/~laci/papers/hypergraphiso.pdf" rel="noreferrer">(see this)</a></p>

CC BY-SA 3.0
2017-08-22T10:14:43.210Z
Why the hyperlink from *supergroup*? That seems to reduce the clarity of the question, not enhance it.
Peter Taylor
CC BY-SA 3.0
2017-08-22T10:19:22.823Z
@ Peter Taylor I Have edited the question
adc
CC BY-SA 3.0
2017-08-22T14:08:29.587Z
Is $G'$ the commutator subgroup of $G$, or a typo?
Emil Jeřábek
CC BY-SA 3.0
2017-08-22T14:12:47.757Z
@ Emil Jeřábek  No $G^{'}$ is not the commutator subgroup of $G$
adc
CC BY-SA 3.0
2017-08-22T14:38:28.910Z
What is it, then?
Emil Jeřábek
CC BY-SA 3.0
2017-08-22T14:50:27.077Z
I have edited the question it was typo
adc
<ds.algorithms><reference-request><gr.group-theory>
How to find largest supergroup in polynomial time?
adc
# How to find largest supergroup in polynomial time?

(Asked by: username_0 on 2017-08-22)

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](https://en.wikipedia.org/wiki/Block_(permutation_group_theory)) 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)](https://people.cs.uchicago.edu/~laci/papers/hypergraphiso.pdf)

**Tags:** ds.algorithms, reference-request, gr.group-theory
> **Comments:**
> **username_1**: Why the hyperlink from *supergroup*? That seems to reduce the clarity of the question, not enhance it.  
> **username_0**: @ Peter Taylor I Have edited the question  
> **username_2**: Is $G'$ the commutator subgroup of $G$, or a typo?  
> **username_0**: @ Emil Jeřábek  No $G^{'}$ is not the commutator subgroup of $G$  
> **username_2**: What is it, then?  
> **username_0**: I have edited the question it was typo  

---

## 1 answers

### Answer by username_3 on 2017-08-22. Score: 6 | Accepted answer

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


---

