AuthorsC. Bessiere, M. B. Belaid and N. Lazaar
TitleComputational Complexity of Three Central Problems in Itemset Mining
AfilliationSoftware Engineering, Scientific Computing
Project(s)Testing of Learning Robots (T-Largo), Testing of Learning Robots (T-LARGO) , Department of Validation Intelligence for Autonomous Software Systems
StatusPublished
Publication TypeTechnical reports
Year of Publication2020
PublisherarXiv
Abstract

Itemset mining is one of the most studied tasks in knowledge discovery. In this paper we analyze the computational complexity of three central itemset mining problems. We prove that mining confident rules with a given item in the head is NP-hard. We prove that mining high utility itemsets is NP-hard. We finally prove that mining maximal or closed itemsets is coNP-hard as soon as the users can specify constraints on the kind of itemsets they are interested in.

URLhttps://arxiv.org/pdf/2012.02619.pdf
Citation Key27664