By applying an old result of Y. Berkovich, we provide a polynomial-time algorithm for computing the minimal possible index of a proper subgroup of a finite permutation group G. Moreover, we find that subgroup explicitly and within the same time if G is given by a Cayley table. As a corollary, we get an algorithm for testing whether or not a finite permutation group acts on a tree non-trivially.
- group representability on trees
- group representability problem
- minimal permutation representation
- permutation group algorithms
- Subgroup of minimal index