TY - GEN

T1 - Generating partial and multiple transversals of a hypergraph

AU - Boros, Endre

AU - Gurvich, Vladimir

AU - Khachiyan, Leonid

AU - Makino, Kazuhisa

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84974555665&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974555665&partnerID=8YFLogxK

U2 - 10.1007/3-540-45022-x_50

DO - 10.1007/3-540-45022-x_50

M3 - Conference contribution

AN - SCOPUS:84974555665

SN - 9783540450221

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 588

EP - 599

BT - Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings

A2 - Montanari, Ugo

A2 - Rolim, Jose D. P.

A2 - Welzl, Emo

PB - Springer Verlag

T2 - 27th International Colloquium on Automata, Languages and Programming, ICALP 2000

Y2 - 9 July 2000 through 15 July 2000

ER -