How to find minimal generating sets efficiently? Let $G$ be a group. A minimal generating set of $G$ is a subset of $R$ of $G$ that generates $G$ such that no proper subset of $R$ also generates $G$. For arbitrary groups is its not true (unlike vector space bases) that two minimal generating sets have the same cardinality. The minimal cardinality of the minimal generating sets of $G$ is denoted by $d(G)$ and the maximal cardinality of the minimal generating sets of $G$ is denoted by $m(G)$ (or sometimes $\mu(G))$. The standard example for groups that have $d(G)\not=m(G)$ is the symmetric groups. In this case Whiston proved that $m(Sym(n))=n-1$ and it is easily shown that $d(Sym(n))=2$.
In the case when $d(G)=m(G)$ then the following procedure can be used to generate a minimal generating set (all of which have the same number of elements). Randomly choose an element $x\in G$ and let $H=\langle x\rangle$. Now choose any element in $y\in G$. If $y\not\in H$ then add $y$ to $H$. If $y\in H$ then choose another element from $G$. Continue until $H=G$. The process will be efficient if there is an efficient way to determine if an element from $G$ is contained within the subgroup $H$. Here efficient means that the number of operations needed is $O(r(\log(|G|)))$  for some polynomial $r$ when $|G|$ finite and some thing else that is appropriate when $G$ is infinite. If this condition is to difficult then we can substitute a weaker definition.
If $G$ satisfies the condition $d(G)=m(G)$ then $G$ is called a $\mathcal{B}$-group and is said to have the weak basis property. A group $G$ is said to have the basis property if all its subgroups are $\mathcal{B}$-groups. Apisa and Klopsch proved that if $G$ is finite then $G$ is a $\mathcal{B}$-group if, and only if, one of the following holds (1) $G$ is a $p$-group for some prime $p$; (2) $G=P\rtimes Q$ where $P$ is a $p$-group and $Q$ is a cyclic $q$-group where $p\not=q$ and such that $C_Q(P)\not=Q$ and then $\mathbb{F}_p[Q/C_Q(P)]$-module $P/\Phi(P)$ is isotypical. A similar result is true for $G$ that have the basis property. These results generalize Burnside's basis theorem which is usually used to show that $p$-groups have $d(G)=m(G)$.
This means that we need only find an efficient membership test for $p$-groups and semidirect products $p-$groups and a cyclic $p$-group (whether the extra structure needed in the generalization of Burnside's theorem is needed is not clear to me) in order to efficiently find minimal generating sets of finite $\mathcal{B}$-groups.
Question 1: Is there an effective membership algorithm for $\mathcal{B}$-groups? I assume that there is from some comments but I as of yet I seem to not see it.
Computing packages like GAP will find minimal generating sets of minimal cardinality (i.e. $d(G)$) when possible). GAP's manual (as pointed out below) states that there are only efficient methods known for computing minimal generating sets of finite solvable groups and of finitely generated nilpotent groups - but does not provide references.
Now finite $\mathcal{B}$-groups are solvable and so they fit into the first category.
Question 2: What are references for these methods (finding minimal generating sets of minimal cardinality for finite solvable groups and of finitely generated nilpotent groups). If no references are possible how different are these methods since finite nilpotent groups are solvable?
Question 3: When $G$ is not a $\mathcal{B}$-group (so $d(G)< m(G)$) and when $G$ is still a finite solvable group or is a finitely generated nilpotent group is there a known relationship between $d(G)$ and $m(G)$ beyond $d(G)<m(G)$?
Such algorithms can be used to help find groups that satisfy properties like: $d(H)<d(K)\leq d(G)$ for all subgroups $e\neq H\lneq K\leq G$ (Which appear to have a similar structure for $\mathcal{B}$-groups or for groups that almost satisfy this property like $n$-qubit Pauli groups. But in general these types of questions are just interesting.
 A: Presumably you're referring to MinimalGeneratingSet. The reference page says

Note that –apart from special cases– currently there are only efficient methods known to compute minimal generating sets of finite solvable groups and of finitely generated nilpotent groups. Hence so far these are the only cases for which methods are available. The former case is covered by a method implemented in the GAP library, while the second case requires the package Polycyclic.

Digging through the source code, it's implemented for finitely generated abelian groups in grppc.gi using Smith Normal Form and a polycyclic generating set. For general polycyclic groups, it's implemented in grppcatr.gi it uses a special polycyclic generating set. I know neither enough GAP nor group theory to competently say more.
A: There are a couple of questions and multiple cases as asked, and it might be worth separating these. I will only consider the case of finite solvable groups here:
If the group is given by a polycyclic presentation, there are effective methods to test membership in subgroups, using induced generating sets. See chapter 8 in:
Holt, Derek F.; Eick, Bettina; O’Brien, Eamonn A.
Handbook of computational group theory.
Discrete Mathematics and its Applications. Boca Raton, FL: Chapman & Hall/CRC Press
A generating set of minimal size for a finite solvable group arises from special polycyclic generating systems. The standard reference for this is:
Cannon, John J.; Eick, Bettina; Leedham-Green, Charles R.
Special polycyclic generating sequences for finite soluble groups.
J. Symb. Comput. 38, No. 5, 1445-1460 (2004), though it does not spell ot the algorithm for such a generating set explicitly. (See the code in the GAP library for such an algorithm, whose correctness follows relatively straightforward from the definitions in the paper).
If the group is not solvable, there are heuristics that give bounds, but the only general algorithm I'm aware of is a rather inefficient exhaustive search.
