2
$\begingroup$

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\}\,\}$

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Take a look at Set cover problem. $\endgroup$ – Eugene Jan 11 '17 at 11:05
  • $\begingroup$ Your problem is a variant of the set cover problem, and is probably NP-complete. So it probably has no polynomial time solution. $\endgroup$ – Yuval Filmus Jan 11 '17 at 11:54
2
$\begingroup$

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).

|cite|improve this answer
$\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.