hide
Free keywords:
-
Abstract:
This paper surveys some recent results on the generation of
implicitly given hypergraphs and their applications in Boolean and integer
programming, data mining, reliability theory, and
combinatorics.
Given a monotone property π over the
subsets of a finite set V, we consider the problem of
incrementally generating the family \cF_π} of all
minimal subsets satisfying property π, when
π is given by a polynomial-time satisfiability oracle.
For a number of interesting monotone properties, the family \cF_{π} turns
out to be {\em uniformly dual-bounded}, allowing for the incrementally
efficient enumeration of the members of \cF_{π.
Important applications include the efficient generation of minimal infrequent
sets of a database (data mining), minimal connectivity ensuring collections of
subgraphs from a given list (reliability theory), minimal feasible solutions to
a system of monotone inequalities in integer variables (integer programming),
minimal spanning collections of subspaces from a given list (linear algebra)
and maximal independent sets in the intersection of matroids (combinatorial
optimization).
In contrast to these results, the analogous problem of generating
the family of all maximal subsets not having property π
is NP-hard for almost all applications mentioned above.
