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