Dual-bounded generating problems: Partial and multiple transversals of a hypergraph

Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

We consider two generalizations of the notion of transversal to a finite hypergraph, the so-called multiple and partial transversals. Multiple transversals naturally arise in 0-1 programming, while partial transversals are related to data mining and machine learning. We show that for an arbitrary hypergraph the families of multiple and partial transversals are both dual-bounded in the sense that the size of the corresponding dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal binary solutions for an arbitrary monotone system of linear inequalities.

Original languageEnglish (US)
Pages (from-to)2036-2050
Number of pages15
JournalSIAM Journal on Computing
Volume30
Issue number6
DOIs
StatePublished - 2000

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Data mining
  • Dualization
  • Hypergraph
  • Incremental polynomial time
  • Independent set
  • Maximal frequent set
  • Minimal infrequent set
  • Monotone boolean function
  • Threshold function
  • Transversal

Fingerprint Dive into the research topics of 'Dual-bounded generating problems: Partial and multiple transversals of a hypergraph'. Together they form a unique fingerprint.

Cite this