Determine wether a set of sets contains a partition of a given set 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.
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.