Computational Complexity of Three Central Problems in Itemset Mining

Many techniques have been developed for itemset mining problems. Famous examples are mining frequent itemsets (Agrawal et al., 1993; Han et al., 2000), mining association rules (Agrawal et al., 1993; Szathmary et al., 2007), mining closed itemsets(Pasquier et al., 1999), mining high utility itemsets (Chan et al., 2003), etc. Most of these works have focused on improving the practical performance of the mining process, but few have conducted a theoretical analysis of the computational complexity of itemset mining problems. Wijsen and Meersman (1998) have proved that it is NPcomplete to decide whether there exists a valid quantitative rule. Angiulli et al. (2001) have proved that the problem of deciding whether there exists a non-redundant association rule of size at least k that is frequent and the problem of deciding whether there exists a non-redundant association rule of size at least k that is confident are both NPcomplete.