Strong generating set-finding problem

Description

Given data

A group $G$ acts faithfully on a finite set $B$ of size $n$. $G$ is specified by means of a generating set $A$ for $G$ (where each element of $A$ is expressed as a permutation on $B$).

Goal

We need to find a strong generating set $S$ for $G$.

Importance

The strong generating set-finding problem is used in algorithms that keep computing generating sets, by trimming down the size of the generating set at every step, to $n^{2}$. For instance, the Schreier-Sims algorithm that solves the membership testing problem given an explicit generating set of the group, appeals to this algorithm for keeping the size of the generating set from growing too large.

Solution

The algorithm to find a strong generating set is sometimes called the Schreier-Sims algorithm. However, this problem that we specifically tackle here is in fact only one part of the Schreier-Sims algorithm, which goes a little farther and tells us how to solve the membership testing problem.