Generating dual-bounded hypergraphs

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

This article 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 ℱπ of all minimal subsets satisfying property π, when π is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family ℱπ turns out to be uniformly dual-bounded, allowing for the incrementally efficient enumeration of the members of ℱπ. 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.

Original languageBritish English
Pages (from-to)749-781
Number of pages33
JournalOptimization Methods and Software
Volume17
Issue number5
DOIs
StatePublished - Oct 2002

Keywords

  • Data mining
  • Enumeration
  • Hypergraph
  • Incremental polynomial time
  • Independent set
  • Integer programming
  • Matroid
  • Maximal frequent set
  • Monotone Boolean function
  • Polymatroid
  • Transversal

Fingerprint

Dive into the research topics of 'Generating dual-bounded hypergraphs'. Together they form a unique fingerprint.

Cite this