TransWikia.com

Maximization problem on finite collection of finite sets

Computer Science Asked by yuezato on November 11, 2021

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?

One Answer

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.

Answered by user114966 on November 11, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP