Algorithm - find the smallest subset of cells representing all the rows

Question

I have several lists, that you can consider as rows of integers. For example :

[1 3 5]
[3 7]
[3 5 7]
[1 5 9]
[3 9]
[1 7]
[5 9 11]

I wish to find the smallest possible set of integers represented on these rows, so that :

• each row has at least one of the selected integers,
• in case of cardinality ties, select the set having the highest sum.

In my example, I believe the result should be [5 7 9] (preferred to [3 5 7] or [1 3 11] or ... many possibilities).

The second part is trivial (selecting highest sum), but the generation of all minimal subsets in cardinality seems to be hard.

Do you know a good way to achieve this ?

Edit

Size of data is growing slowly with iterations, but I need exact matches.

Answer 1

The minimum cardinality version is NP-Complete. Set Cover can be reduced to this. Requiring the max among those only makes the problem harder.

Btw, the other answer talking about boolean satisfiability is wrong! You need to reduce boolean satisfiability to this problem to show NP-Completeness, not the other way round.

Set cover is basically:

Give a collection of sets S1, S2, ... Sn of subsets of a set X, find the smallest sub-collection (in terms of number of sets) whose union covers all the elements in S1 U S2 U ... U Sn.

To reduce this to our problem,

Let S = S1 U S2 ... U Sn. = {x1 , x2, ..., xm}

Let C_i = { j such that xi is in Sj }

Feed the C_i to our problem.

Now if our problem was solvable in polynomial time and we could find a minimum cardinality set of elements of C_i, then we can find a set cover for the Si and vice versa.

This can normally be solved as an integer programming problem (which is NP-Hard too).

For approximate solutions, this can be viewed as a linear programming problem (which has polynomial time algorithms) and randomized rounding can be done to convert fractional values (solutions to the LP) to integers.

Also, unfortunately, it has been shown that this is NP-hard to approximate to even a constant factor (in fact I believe it is O(logn)).