A lower bound for the HBC transversal hypergraph generation

Khaled Elbassioni, Matthias Hagen, Imran Rauf

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The computation of transversal hypergraphs in output-polynomial time is a long standing open question. An Apriori-like level-wise approach (referred to as the HBC-algorithm or MTminer) was published in 2007 by Hébert, Bretto, and Crémilleux [A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundamenta Informaticae, 80(4), 2007, 415-433] and was experimentally demonstrated to have very good performance on hypergraphs with small transversals. In this short note extending the paper by Hagen [Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157(7), 2009, 1460-1469], we prove a superpolynomial lower bound for the HBC-algorithm. This lower bound also shows that the originally claimed upper bound on the HBC-algorithm's running time is wrong.

Original languageBritish English
Pages (from-to)409-414
Number of pages6
JournalFundamenta Informaticae
Issue number4
StatePublished - 2014


  • algorithm analysis
  • HBC-algorithm
  • lower bound
  • MTminer
  • transversal hypergraph generation


Dive into the research topics of 'A lower bound for the HBC transversal hypergraph generation'. Together they form a unique fingerprint.

Cite this