## DIMACS TR: 2000-17

## Generating Weighted Transversals of a Hypergraph

### Authors: Endre Boros, Vladimir Gurvich, Leonid Khachiyan and Kazuhisa Makino

**
ABSTRACT
**

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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-17.ps.gz

DIMACS Home Page