Abstract. Let A be an m×n binary matrix, t ∈ {1, . . . , m} be a threshold, and ε > 0 be a positive parameter. We show that given a family of O(n ε ) maximal t-frequent column sets for A, it is NP-complete to decide whether A has any further maximal t-frequent sets, or not, even when the number of such additional maximal t-frequent column sets may be exponentially large. In contrast, all minimal t-infrequent sets of columns of A can be enumerated in incremental quasi-polynomial time. The proof of the latter result follows from the inequality α ≤ (m − t + 1)β, where α and β are respectively the numbers of all maximal t-frequent and all minimal t-infrequent sets of columns of the matrix A. We also discuss the complexity of generating all closed t-frequent column sets for a given binary matrix.
Boros et al. REF showed that, given a family of O(n ε ) maximal frequent patterns, it is NP-complete to decide whether X has any further maximal frequent patterns (for arbitrarily small fixed ε > 0), and that all minimal infrequent patterns can be enumerated in incremental quasipolynomial time.
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets
STACS
Mathematics Computer Science