Fixed size set to contain the maximum number of gi

Question

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?

Checking each of 100!/(80!*20!) sets, is inefficient.

Answer 1

I am not so sure this is NP complete.

Consider the related problem where we get a reward of x for each set, but have to pay a price of y for each number that we want to allow. (A set only pays the reward if all the numbers it contains have been paid for.)

You can solve this type of problem using the max flow algorithm by:

1. Setting up a source node
2. Setting up a destination node
3. Setting up a node for each set
4. Setting up a node for each number
5. Add edge from source to each set with capacity x
6. Add edge from each number to dest with capacity y
7. For each number a in set s, add edge from s to a with infinite capacity

Solving the maximum flow problem on this graph (from the source to destination node) finds a minimum cut cost c.

The net amount of money we would make would be N.x-c (where N is the number of sets).

If we can choose y (e.g. by bisection) such that we have selected exactly 20 numbers, then we have managed to solve for the maximum number of sets with 20 numbers.