3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.