A Lower Bound for the HBC Transversal Hypergraph Generation

• Autorzy: Elbassioni K. , Hagen M. , Rauf I.

Identyfikatory

DOI

10.3233/FI-2014-997

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 4
• Strony: 409--414
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Elbassioni K.

• Masdar Institute of Science and Technology, Abu Dhabi, UAE

autor

Hagen M.

• Bauhaus-Universität Weimar, D–99423 Weimar, Germany

autor

Rauf I.

• National University of Computer and Emerging Sciences, Karachi, Pakistan

Bibliografia

• [1] Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases, Proceedings of VLDB 1994.
• [2] Bailey, J., Manoukian, T., Ramamohanarao, K.: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, Proceedings of ICDM 2003.
• [3] Berge, C.: Hypergraphs, vol. 45 of North-Holland Mathematical Library, North-Holland, 1989.
• [4] Dong, G., Li, J.: Mining border descriptions of emerging patterns from dataset pairs, Knowledge and Information Systems, 8(2), 2005, 178–202.
• [5] Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems, SIAM Journal on Computing, 24(6), 1995, 1278–1304.
• [6] Elbassioni, K. M.: On the complexity of the multiplication method for monotone CNF/DNF dualization, Proceedings of ESA 2006.
• [7] Elbassioni, K. M., Hagen, M., Rauf, I.: Some fixed-parameter tractable classes of hypergraph duality and related problems, Proceedings of IWPEC 2008.
• [8] Fredman, M. L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, 21(3), 1996, 618–628.
• [9] Gurvich, V., Khachiyan, L.: On the frequency of the most frequently occurring variable in dual monotone DNFs, Discrete Mathematics, 169(1-3), 1997, 245–248.
• [10] Hagen, M.: On the fixed-parameter tractability of the equivalence test of monotone normal forms, Information Processing Letters, 103(4), 2007, 163–167.
• [11] Hagen, M.: Algorithmic and Computational Complexity Issues of MONET, Ph.D. Thesis, Friedrich-Schiller-Universität Jena, 2008.
• [12] Hagen, M.: Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157(7), 2009, 1460–1469.
• [13] Hébert, C., Bretto, A., Crémilleux, B.: A data mining formalization to improve hypergraph minimal transversal computation, Fundamenta Informaticae, 80(4), 2007, 415–433.
• [14] Johnson, D. S., Papadimitriou, C. H., Yannakakis, M.: On generating all maximal independent sets, Information Processing Letters, 27(3), 1988, 119–123.
• [15] Kavvadias, D. J., Stavropoulos, E. C.: An efficient algorithm for the transversal hypergraph generation, Journal of Graph Algorithms and Applications, 9(2), 2005, 239–264.
• [16] Papadimitriou, C. H.: NP-Completeness: A Retrospective, Proceedings of ICALP 1997.
• [17] Takata, K.: A worst-case analysis of the sequential method to list the minimal hitting sets of a hypergraph, SIAM Journal on Discrete Mathematics, 21(4), 2007, 936–946.