Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation

by    Matthias Hagen

Preprint series: 06-08, Reports on Computer Science

MSC:
68W40 Analysis of algorithms [See also 68Q25]

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
problem---the sequential
method of Berge [Ber89]---is not
output-polynomial
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
cases [BMR03,DL05,KS05].
Nevertheless, a theoretical analysis was
still pending.
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

Upload: 2006-06-21

Update: 2006-06-21


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.