Computational Complexity of Three Central Problems in Itemset Mining
This work establishes fundamental complexity limits for itemset mining problems, which is important for researchers and practitioners developing efficient algorithms in data mining.
This paper analyzes the computational complexity of three core itemset mining problems. It proves that mining confident rules with a given item in the head is NP-hard, mining high utility itemsets is NP-hard, and mining maximal or closed itemsets is coNP-hard when user-defined constraints are present.
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.