An inequality limiting the number of maximal frequent sets

Authors: E. Boros,V. Gurvich, L. Khachiyan and K. Makino

ABSTRACT

Given an arbitrary $m\times n$ binary matrix $A$ and a threshold $t \in \{1, \ldots, m\}$, a subset $C$ of the columns is called $t$-{\em frequent} if there are at least $t$ rows having a $1$ in each of these columns, and otherwise $C$ is called $t$-{\em infrequent}. Denoting by $\alpha$ the number of maximal $t$-frequent, and by $\beta$ the number of minimal $t$-infrequent column sets in the given matrix $A$, we prove that the inequality $\alpha \leq (m-t+1)\beta$ holds. This inequality is sharp, and allows for an incremental quasi-polynomial algorithm for generating all minimal $t$-infrequent sets, while the analogous problem for maximal $t$-frequent sets is NP-hard. Our proof is based on an inequality from extremal set theory, which may be of independent interest.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-37.ps.gz