Algorithms for the Minimum Generating Set Problem

MaRDI QIDQ6436585zbMATH OpenFDO

Authors Bireswar Das, Dhara Thakkar

Publication date 15 May 2023

Abstract: For a finite group $G$, the size of a minimum generating set of $G$ is denoted by $d(G)$. Given a finite group $G$ and an integer $k$, deciding if $d(G)leqk$ is known as the minimum generating set (MIN-GEN) problem. A group $G$ of order $n$ has generating set of size $lceillo{g}_{p}nceil$ where $p$ is the smallest prime dividing $n=|G|$. This fact is used to design an $n^{lo{g}_{p}n+O(1)}$-time algorithm for the group isomorphism problem of groups specified by their Cayley tables (attributed to Tarjan by Miller, 1978). The same fact can be used to give an $n^{lo{g}_{p}n+O(1)}$-time algorithm for the MIN-GEN problem. We show that the MIN-GEN problem can be solved in time $n^{(1/4)lo{g}_{p}n+O(1)}$ for general groups given by their Cayley tables. This runtime incidentally matches with the runtime of the best known algorithm for the group isomorphism problem. We show that if a group $G$, given by its Cayley table, is the product of simple groups then a minimum generating set of $G$ can be computed in time polynomial in $|G|$. Given groups $G_i$ along with $d(G_i)$ for $iin[r]$ the problem of computing $d(P{i}_{iin[r]}{G}_i)$ is nontrivial. As a consequence of our result for products of simple groups we show that this problem also can be solved in polynomial time for Cayley table representation. For the MIN-GEN problem for permutation groups, to the best of our knowledge, no significantly better algorithm than the brute force algorithm is known. For an input group $Gleq{S}_n$, the brute force algorithm runs in time $|G{|}^{O(n)}$ which can be $2^{Omega(n^2)}$. We show that if $Gleq{S}_n$ is a primitive permutation group then the MIN-GEN problem can be solved in time quasi-polynomial in $n$. We also design a $mathrmDTIME(2^n)$ algorithm for computing a minimum generating set of permutation groups all of whose non-abelian chief factors have bounded orders.

This page was built for publication: Algorithms for the Minimum Generating Set Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436585)