## DIMACS TR: 2002-23

## Generating Dual-Bounded Hypergraphs

### Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

**
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 $\pi$ over the
subsets of a finite set $V$, we consider the problem of
incrementally generating the family $\cF_{\pi}$ of all
minimal subsets satisfying property $\pi$, when
$\pi$ is given by a polynomial-time satisfiability oracle.
For a number of interesting monotone properties, the family $\cF_{\pi}$
turns out to be {\em uniformly dual-bounded}, allowing for the
incrementally
efficient enumeration of the members of $\cF_{\pi}$.

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 $\pi$ is NP-hard
for most of the monotone properties $\pi$ considered in the paper.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-23.ps.gz

DIMACS Home Page