4
$\begingroup$

I asked this question in SO here

I have about 1000 sets of size <=5 containing numbers 1 to 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... 

Is it possible to find a set of size 20 that contains the maximum number of given sets?

In other words, let $U = \{1, 2, ..., 100\}$ and $S \subseteq \{Z \in 2^U \mid |Z| \leq 5\}$. How can I find $X \subseteq U$ with $|X| = 20$ such that $|\{Y \in S \mid Y \subseteq X\}|$ is maximized?

Checking each of 100!/(80!*20!) sets or bulding all set combinations with size <=20 is inefficient.

Is there any (semi)efficient solution or is it np-complete?

The set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} contains 5 sets.

$\endgroup$
  • 1
    $\begingroup$ Without the bounds on the number of sets and the number of numbers, it's NP-hard by an objective-preserving reduction from densest k-subgraph. There may be a practically efficient solution anyway for the instances that you care about. $\endgroup$ – David Eisenstat Oct 21 '14 at 13:25
  • $\begingroup$ Please don't cross-post on multiple StackExchange sites. Cross-posting violates site rules. If you'd like to draw more attention to your question, you can post a bounty. If you posted it on the wrong site initially and you notice it quickly enough, you can flag it for moderator attention and ask them to migrate it to a different site. Cross-posting fragments answers and causes people to duplicate work. $\endgroup$ – D.W. Oct 21 '14 at 18:46
  • $\begingroup$ This question can be viewed as a nice variant of the Knapsack problem where we would like to pack sets into a bag of size $|X|$, but the size of each set is dependent on the previous sets packed into the bag. $\endgroup$ – R B Oct 27 '14 at 15:02
  • $\begingroup$ I think the repost may be fair in this case; you should maybe argue why the answer given on Stack Overflow did not satisfy you. (cc @D.W.) Note, though, that you need to formulate a general problem in order to get a meaningful computer science answer: every single instance of a problem has a fixed answer, so there is a trivial algorithm that outputs this answer in linear (in the output size) time. $\endgroup$ – Raphael Oct 27 '14 at 16:47
  • $\begingroup$ feel there is interesting question buried in here somewhere but that it has been not formally stated very well. hint: use subscripts to denote different sets. (etc) suggest drop by Computer Science Chat to work out the details $\endgroup$ – vzn Oct 27 '14 at 17:43
4
+50
$\begingroup$

The decision version of the problem can be formulated as follows:

  • Given a collection of sets of numbers $S$. Each number is drawn from a set $U$. You want to know if there is a way to pick $k$ numbers from $U$ to form a set $X$ which is the superset of $s$ sets in $S$.

The following is a reduction from k-clique which is an NP-complete problem.

The k-clique problem has an input as a graph and asks if there is a way to pick $k$ nodes so that there is an edge between any two of the $k$ nodes.

We turn each node into a number. These numbers form the set $U$. We turn each edge into a set containing two numbers representing the corresponding two nodes of the edge. These sets form the set $S$.

The question to the original problem is: Is there a way to pick $k$ numbers from $U$ to form a set $X$ such that $X$ is the superset of $C_{2}^k$ sets in $S$

The proof has two directions.

  1. If there is a k-clique in the graph, then we can pick the $k$ numbers corresponding to $k$ nodes in the clique to form $X$. Because of the way we transform the graph, we know there will be $C_{2}^k$ sets in $S$ each corresponds to an edge in the original graph and thus is a subset of $X$. So the answer to the original problem is positive.
  2. If there is no clique of size $k$, then for any set of $k$ nodes chosen from the graph one can only have less than $C_{2}^k$ undirected edges between any two picked nodes. Otherwise, we will have a clique of size $k$. This means that there can only be less than $C_{2}^k$ subsets of $S$ which is a subset of the set $X$ formed by any $k$ chosen numbers. So the answer to the original problem is not positive.

The transformation is in poly-time. The reduction is proven, so the problem is NP-hard. The problem is clearly in NP because we check how many sets covered by $k$ numbers in poly time. This means the original problem is NP-complete.

$\endgroup$

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.