2
$\begingroup$

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$ ?

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

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.

$\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.