# Find sets with given union

We are given positive integers $n$, $m$ and a set $S$ of subsets of the set $\{1,2,...,n\}$ with $|S| = m$.

For example:

$n = 5,\,\, m = 4,\,\, S = \{\, \{1,2\}, \{1,3\}, \{4,5\}, \{2,3\} \,\}.$

What is the fastest way to find the minimal subset $S'$ of $S$ such that the union of sets in $S'$ is equal to $\{1,2,...,n\}$.

In our example, there are 3 possible answers:

$S' = \{\,\{1,2\}, \{1,3\}, \{4,5\}\,\} \\ S' = \{\,\{1,2\}, \{2,3\}, \{4,5\}\,\} \\ S' = \{\,\{1,3\}, \{2,3\}, \{4,5\}\,\}$

• Take a look at Set cover problem. – Eugene Jan 11 '17 at 11:05
• Your problem is a variant of the set cover problem, and is probably NP-complete. So it probably has no polynomial time solution. – Yuval Filmus Jan 11 '17 at 11:54

Given $$U=\{1,\ldots , n\}$$ and $$S\subseteq 2^U$$, integer $$k$$
Decide whether $$C\subseteq S$$ exists s.t. $$\cup_{X \in C} X = U$$ and $$|C| \leq k$$