# Maximization problem on finite collection of finite sets

## 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?

• I think I understand why $\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}$ is of advantage (there may be one $\cap G$ missing in both explications). I fail to see the value of maximising $|G|$, let alone multiplying that to the former: please provide the intuition for that goal. – greybeard Jul 25 '20 at 8:24
• @greybeard Thank you for your interesting. I try to answer your questions. 1. Is maximizing | \bigcap G | useful ? This problem equals to find one of the largest set $X_i$ from $\mathcal{F}$ and it can be solved in linear time. BTW, I've found this pdf about "Maximum k-Subset Intersection" (MSI) problem. On this, for a given $k$, we find a collection $H \subseteq \mathcal{F}$ with $|H| = k$ that maximizes $| \bigcap H |$. This is also interesting!! The paper shows MSI and Maximum-edge biclique problem are closely related. – yuezato Jul 26 '20 at 16:07
• 2. How do we use this problem? Let me explain my original motivation, compactifying finite collections of finite sets, by reusing the above instance. On the example, the collection $\mathcal{F}$ can be rephrased as follows by using $\bigcap G = \{ a, b, c \}$: $$\mathcal{F} \approx \langle \mathcal{G} = \{a, b, c\} \&\& \{ \mathcal{G}, \mathcal{G} \cup x, \{ b, c, y \}, \mathcal{G} \cup z \} \rangle.$$ Using $\bigcap G$, we can obtain the shorter representation. To this end, I need the above problem rather than MSI. I hope these will help. – yuezato Jul 26 '20 at 16:09

• The edge $$(u,v)$$ means that $$u \in v$$.