Subgroups of minimal index in polynomial time

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number2050010
Number of pages4
JournalJournal of Algebra and its Applications
Issue number1
Publication statusPublished - 1 Jan 2020


  • group representability on trees
  • group representability problem
  • minimal permutation representation
  • permutation group algorithms
  • Subgroup of minimal index


Dive into the research topics of 'Subgroups of minimal index in polynomial time'. Together they form a unique fingerprint.

Cite this