Algorithms for the Minimum Generating Set Problem
share
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)≤ k is known as the minimum generating set (MIN-GEN) problem. A group G of order n has generating set of size ⌈log_p n ⌉ where p is the smallest prime dividing n=|G|. This fact is used to design an n^log_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^log_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)log_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 i∈ [r] the problem of computing d(Π_i∈[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 G≤ S_n, the brute force algorithm runs in time |G|^O(n) which can be 2^Ω(n^2). We show that if G≤ 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 DTIME(2^n) algorithm for computing a minimum generating set of permutation groups all of whose non-abelian chief factors have bounded orders.
READ FULL TEXT