DIMACS TR: 99-62
Dual-Bounded Hypergraphs: Generating Partial and Multiple
Transversals
Authors: E. Boros, V. Gurvich, L. Khachiyan and K. Makino
ABSTRACT
We consider two natural generalizations of the notion of
transversal to a
finite hypergraph, so called {\em multiple} and {\em 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 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 generation 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 Boolean solutions for an arbitrary monotone system of linear
inequalities.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-62.ps.gz
DIMACS Home Page