Problem
I am considering the following maximization problem:
- Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
- Goal is to find a subset $G \subseteq \mathcal{F}$ that maximizes $|G| \times |\bigcap G|$ where
- $|G|$ is the cardinality of the set $G$, and
- $\bigcap G = \bigcap \{X_{i_1}, X_{i_2}, \ldots, X_{i_m} \} = X_{i_1} \cap X_{i_2} \cap \cdots \cap X_{i_m}$.
As an example, for the collection $$ \mathcal{F} = \{ \{a, b, c\}, \{a, b, c, x\}, \{b, c, y\}, \{a, b, c, z\} \}, $$ the maximizing subset is $G = \{ \{a, b, c\}, \{a, b, c, x\}, \{a, b, c, z\} \}$ and the score is $3 \times |\{a, b, c\}| = 9$.
Note: the score of $\mathcal{F}$ itself is $4 \times |\{b, c\}| = 8$.
Question
I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets). However, I don't have any good idea to solve this problem efficiently. As yow know, we can solve this by enumerating all the collections of $\mathcal{F}$; but, it's too slow for practical use.
Is there a polynomial-time or some kind of efficient algorithm for this problem? Or, does this problem belong to the complexity class that cannot be solved in polynomial time?