by Matthias Hagen
Preprint series: 06-08, Reports on Computer Science
Abstract: The computation of all minimal transversals
of a given hypergraph in output-polynomial
time is a long standing open question known
as the transversal hypergraph generation.
One of the first attempts on this
method of Berge [Ber89]---is not
as shown by Takata [Tak02].
In recent years, three new algorithms
designed to improve the sequential method
were published and experimentally shown
to perform well on practically relevant
Nevertheless, a theoretical analysis was
We close this gap by proving lower bounds
for all three algorithms.
Our lower bounds show that
none of the algorithms is output-polynomial.
Keywords: transversal hypergraph generation, lower bound, output-polynomial time