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

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan

    Research output: Contribution to journalArticleAcademicpeer-review

    951 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)558-565
    JournalSIAM Journal on Computing
    Volume9
    Issue number3
    DOIs
    Publication statusPublished - 1980

    Fingerprint

    Dive into the research topics of 'Generating all maximal independent sets : NP-hardness and polynomial-time algorithms'. Together they form a unique fingerprint.

    Cite this