Determine wether a set of sets contains a partition of a given set

Question

Consider the following problem :

Given a set of sets of integers, $\Sigma = \{S_i, i \in I\}$, and a set G, determine wether $\Sigma$ contains a partition of G, i.e. a set $J \subseteq I$ such that $G = \bigsqcup_{j\in J} S_j$.

This problem is (if i'm not mistaken) in NP.

I'm trying to determine wether this problem is in P (Or maybe NP-complete).

• Do you know if this problem is treated anywhere in the litterature (Algorithm or NP Completeness) ?
• Do you know any problems that are close to this one ?

I have tried to design a polynomial algorithm for the problem, but nothing working so far.

Answer 1

Without loss of any really interesting aspect, we can assume that $S_i\subseteq G$ for all $i\in I$. Otherwise, we can we can remove each $S_i$ which is not a subset of $G$. This reduction step takes $O(ng)$ times, where $n=\sum_{i\in I}|S_i|$ and $g=|G|$.

Now that $S_i\subseteq G$, this problem is the exact cover problem, which is one of Karp's 21 NP-complete problems. You can find all sort of information about it at its Wikipedia entry.

I have played briefly a game called Pentomino, which is an exact cover problem.