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$ – Peter Taylor Aug 22 '17 at 10:14
  • $\begingroup$ @ Peter Taylor I Have edited the question $\endgroup$ – adc Aug 22 '17 at 10:19
  • $\begingroup$ Is $G'$ the commutator subgroup of $G$, or a typo? $\endgroup$ – Emil Jeřábek Aug 22 '17 at 14:08
  • $\begingroup$ @ Emil Jeřábek No $G^{'}$ is not the commutator subgroup of $G$ $\endgroup$ – adc Aug 22 '17 at 14:12
  • $\begingroup$ What is it, then? $\endgroup$ – 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]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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