Abstract:
Bases, subgroup towers and strong generating sets (SGSs) have played a key role
in the development of algorithms for permutation groups. We analyze the computational
complexity of several problems involving bases and SGSs, and we use subgroup towers
and SGSs to construct dense networks with practical routing schemes.
Given generators for G ≤ Sym(n), we prove that the problem of computing a
minimum base for G is NP-hard. In fact, the problem is NP-hard for cyclic groups and
elementary abelian groups. However for abelian groups with orbits of size less than 8, a
polynomial time algorithm is presented for computing minimum bases. For arbitrary permutation groups a greedy algorithm for approximating minimum
bases is investigated. We prove that if G ≤ Sym(n) with a minimum base of size k, then
the greedy algorithm produces a base of size Ω (k log log n).