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

We consider two generalizations of the notion of transversal to a finite hy pergraph, the so-called multiple and partial transversals. Multiple transve rsals naturally arise in 0-1 programming, while partial transversals are re lated to data mining and machine learning. We show that for an arbitrary hy pergraph the families of multiple and partial transversals are both dual-bo unded in the sense that the size of the corresponding dual hypergraph is bo unded by a polynomial in the cardinality and the length of description of t he input hypergraph. Our bounds are based on new inequalities of extremal s et 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 g eneration 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.