Generating partial and multiple transversals of a hypergraph

Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

We consider two natural generalizations of the notion of transversal to a finite hypergraph, arising in data-mining and machine learning, the so called multiple and partial transversals. We show that the hypergraphs of all multiple and all partial transversals are dual- bounded in the sense that in both cases, the size of the 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 logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals of an arbitrary hypergraph are polynomial-time reducible to the well-known dualization problem of 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 Boolean solutions for an arbitrary monotone system of linear inequalities. Thus, it is unlikely that these problems are NP-hard.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
EditorsUgo Montanari, Jose D. P. Rolim, Emo Welzl
PublisherSpringer Verlag
Pages588-599
Number of pages12
ISBN (Print)9783540450221
DOIs
StatePublished - 2000
Event27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland
Duration: Jul 9 2000Jul 15 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1853
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other27th International Colloquium on Automata, Languages and Programming, ICALP 2000
Country/TerritorySwitzerland
CityGeneva
Period7/9/007/15/00

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Generating partial and multiple transversals of a hypergraph'. Together they form a unique fingerprint.

Cite this