We consider a generalization of the notion of transversal to a finite hypergraph, so called {\em weighted transversals}. Given a non-negative weight vector assigned to each hyperedge of the input hypergraph, we define a weighted transversal as a minimal vertex set which intersects a collection of hypereredges of sufficiently large total weight. We show that the hypergraph of all weighted transversals is dual-bounded, i.e, the size of its dual hypergraph is polynomial in the number of weighted transversals and the size 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. For instance, we show that for any threshold frequency, the number of maximal frequent sets of columns in a binary matrix is bounded by the number of minimal infrequent sets of columns in the same matrix multiplied by the number of its rows. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal infrequent sets of columns for a given binary matrix.
DIMACS Home Page