A Worst-Case Analysis of the Sequential Method to List the Minimal Hitting Sets of a Hypergraph
Ken Takata · SIAM Journal on Discrete Mathematics · 2007
It is open whether the minimal hitting sets of a hypergraph can be listed in time polynomial in the input and output size. We show that a well-known sequential approach described by Berge and studied since the 1950s is not polynomial in the above sense, even if we allow an optimal ordering of the edges. This answers a question posed by H. Hirsh. The proof uses hypergraphs based on read-once formulas. We also offer a generalization of this sequential approach.