# Fixed size set to contain the maximum number of given sets

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.

• 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. – David Eisenstat Oct 21 '14 at 13:25
• 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. – D.W. Oct 21 '14 at 18:46
• 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. – R B Oct 27 '14 at 15:02
• 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. – Raphael Oct 27 '14 at 16:47
• 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 – vzn Oct 27 '14 at 17:43

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.