Generating all maximal independent sets: NP-hardness and polynomial-time algorithms
EL Lawler, JK Lenstra, AHG Rinnooy Kan - SIAM Journal on Computing, 1980 - SIAM
EL Lawler, JK Lenstra, AHG Rinnooy Kan
SIAM Journal on Computing, 1980•SIAMSuppose that an independence system (E,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 P=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, eg the efficient generation of all maximal feasible solutions to a …
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 P=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, eg the efficient generation of all maximal feasible solutions to a …
Suppose that an independence system 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 and K, unless . 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.