2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – greybeard Jul 25 '20 at 8:24
  • $\begingroup$ @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. $\endgroup$ – yuezato Jul 26 '20 at 16:07
  • $\begingroup$ 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. $\endgroup$ – yuezato Jul 26 '20 at 16:09
3
$\begingroup$

This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where

  • The left side corresponds to elements
  • The right side corresponds to sets
  • The edge $(u,v)$ means that $u \in v$.

Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete", the decision problem is NP-complete.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks so much for your great answer! I'd have explored a useful variant of the (biparate) maximum matching, but I couldn't. Your answer, "the maximum edge biclique problem", quite naturally encodes my problem. Reading the mentioned and some related papers, I've also understood to develop an approximating algorithm may be hard. $\endgroup$ – yuezato Jul 21 '20 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.