# An efficient method to compute a minimum set of sets that form the union of these sets?

Let's say we have a set of sets:

$$\mathfrak S = \lbrace S_1, S_2, ... , S_n\rbrace$$

And the union of the all the sets in this set:

$$\mathfrak U = \bigcup\limits_{i=1}^{n} S_{i}$$

And so there is at least one minimum set of sets that is identical to this union:

$$(\mathfrak M \subseteq \mathfrak S) = \mathfrak U$$

What is the most efficient known method of computing $\mathfrak M$ ?

• What is the nature of these sets? Finite, countable, etc.? You probably mean the Set Cover problem which is NP-complete. – fade2black Aug 10 '17 at 18:39
• Also, what do you mean by "...that is identical to this union"? Union of sets belonging to $\mathfrak M$? – fade2black Aug 10 '17 at 18:49
• @fade2black: thank you, the Set Cover problem is exactly what I meant – Mothomoticks Aug 10 '17 at 19:02
• @fade2black Make an answer? – Yuval Filmus Aug 10 '17 at 19:11

In case $S_i$ sets are finite your problem is reduced to the Set Cover problem which is NP-complete. You can also attack this problem by any approximation algorithm, e.g. Greedy algorithm, or by using Linear programming.