Generating all maximal independent sets : NP-hardness and polynomial-time algorithms

Suppose that an independence system $(E,\mathcal {I})$ is characterized by a subroutine which indicates in unit time whether or not a given subset of $E$ is independent. It is shown that there is no algorithm for generating all the $K$ maximal independent sets of such an independence system in time polynomial in $|E|$ and $K$, unless $\mathcal {P} = \mathcal {NP}$. However, it is possible to apply ideas of Paull and Unger and of Tsukiyama et al. to obtain polynomial-time algorithms for a number of special cases, e.g. the efficient generation of all maximal feasible solutions to a knapsack problem. The algorithmic techniques bear an interesting relationship with those of Read for the enumeration of graphs and other combinatorial configurations.