New Results on Monotone Dualization and Generating Hypergraph Transversals

Thomas Eiter, Georg Gottlob, Kazuhisa Makino

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open proble…