Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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\}\,\}$
This is related to the Hitting-Set-Decision-Problem:
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$
The problem is NP-COMPLETE and thus we do not know whether a polynomial algorithm exists. The optimization problem which you refer to is NP-hard. There are approximation algorithms (see wikipedia).
