The Transversal Hypergraph Generation problem

The Transversal Hypergraph Generation problem is the problem of generating all minimal hitting sets (transversals) of a hypergraph.

Kavvadias and Stavropoulos have implemented an efficient algorithm for the problem [WAE99, JGAA05].

A linux-executable is available here (use switch -h for help).

Selected publications on the problem

• J. Bailey, T. Manoukian, and K. Ramamohanarao. fast algorithm for computing hypergraph transversals and its application in mining emerging paterns. In Proc. of the 3rd IEEE International Conference on Mining (ICDM 2003), pages 485-488, IEEE Computer Society, December 2003.
• E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals. In Proc. of the 11th European Symposioum in Algorithms (ESA 2003), volume 2432 of LNCS, pages 556-567. Springer, 2003.
• T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal of Computing, 24(6):1278-1304, December 1995.
• T. Eiter and G. Gottlob. Hypergraph transversal computation and related problems in Logic and AI. In Proc. of the 8th European Conference on Logics in Artificial Intelligence (JELIA 2002), volume 2424 of LNCS/LNAI, pages 549-564. Springer, 2002.
• T. Eiter, G. Gottlob, and K. Makino. New results on monotone dualization and generating hypergraph transversals. SIAM J. Computing, 32(2):514-537, 2003.
• M. L. Fredman and L. Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21:618-628, 1996.
• D. J. Kavvadias, M. Sideri, and E. C. Stavropoulos. Generating all maximal models of a Boolean expression. Information Processing Letters, 74(3-4):157-162, May 2000.
• [WAE99] D. J. Kavvadias and E. C. Stavropoulos, Evaluation of an Algorithm for the Transversal Hypergraph Problem. In Proc. of the 3rd Workshop on Algorithm Engineering (WAE'99), LNCS 1668, pp. 72-84, 1999. [pdf]
• D. J. Kavvadias and E. C. Stavropoulos. Monotone Boolean dualization is in co-{NP}[$\log^2n$]. Information Processing Letters, 85(1):1--6, January 2003.
• [JGAA05] D. J. Kavvadias and E. C. Stavropoulos, An Efficient Algorithm for the Transversal Hypergraph Generation. Journal of Graph Algorithms and Applications, 9(2):239--264, 2005. [pdf]