4
$\begingroup$

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are trying to form words such that each letter is used exactly once and all of the words collectively use all of the letters. Prove that this problem is NP-complete.

I thought that showing Set Packing $\le_p$ Using Up All Letters would be sufficient to show that the problem is NP-Complete. However, I'm having some trouble showing that if we have a set packing instance, then this implies there is a Using Up All Letters instance.

So suppose we have a Set Packing instance defined in the sense of the Wikipedia article. How does this show that there is an equivalent Using Up All Letters instance?

I know how to go in the reverse direction: suppose we have a Using Up All Letters instance, then we know this is also a Set Packing instance merely by how the problem of Using Up All Letters is defined (the universe is all of the letters, and the set of words that "covers" the universe is disjoint by definition). But, again, I'm having trouble going in the other direction.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

You don't need a reduction; the problem you describe is known as EXACT COVER and it is one of the 21 decision problems Richard Karp proved $NP$-complete in 1972.

From Wikipedia:

Given a collection $S$ of subsets of a set $X$, an exact cover of $X$ is a subcollection $S^*$ of $S$ that satisfies two conditions:

  • The intersection of any two distinct subsets in $S^*$ is empty, i.e., the subsets in $S^*$ are pairwise disjoint. In other words, each element in $X$ is contained in at most one subset in $S^*$.
  • The union of the subsets in $S^*$ is $X$, i.e., the subsets in $S^*$ cover $X$. In other words, each element in $X$ is contained in at least one subset in $S^*$.

$X$ is the collection of letters on the refrigerator.

$S$ is the collection of words that your daughter knows that are made up of letters in $X$.

$S^*$ is a subcollection of words from $S$ that exactly cover $X$.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ I think you're assuming there are no duplicate letters. $\endgroup$ – NovaDenizen Nov 14 '14 at 5:52
  • 1
    $\begingroup$ The duplicates can be treated as distinct entities as far as set intersection and union are concerned. It's still the same problem. $\endgroup$ – Kyle Jones Nov 14 '14 at 6:04
  • 1
    $\begingroup$ But then you have to include many multiples of candidate words (possibly exponentially many) as the size of the alphabet or problem increases. I think this problem maps to what is called a multiset multicover problem, but I can't find a good definition or description for that. $\endgroup$ – NovaDenizen Nov 14 '14 at 6:19
0
$\begingroup$

It seems like it would be easier to do a reduction from 3-Dimensional Matching, where you're explicitly trying to cover all the elements of your ground set.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Why do you believe this is true? $\endgroup$ – Cortney Nov 14 '14 at 3:06
  • $\begingroup$ 3DM (in particular, the special case where all sets have the same size and you want a perfect matching) is a special case of set packing, so there are fewer instances that you need to transform into "Using Up Letters". It seems like the main problem in transforming Set Packing into "Using Up Letters" is that an arbitrary Set Packing instance could have a solution that doesn't use every element. Reducing from 3DM means you don't have to worry about those instances. $\endgroup$ – Gregory J. Puleo Nov 14 '14 at 3:08
  • $\begingroup$ But how can we define a 3DM instance to a be a Using Up Letters instance? I don't quite see the equivalence so clearly. $\endgroup$ – Cortney Nov 14 '14 at 3:11
  • $\begingroup$ I'm assuming that the "dictionary" of valid words is part of the "Using Up Letters" instance -- if the input is actually just the letters and you're forced to use real English words, then doing the reduction seems a lot harder. Under this assumption, each vertex in the 3DM instance should correspond to a letter in the UUL instance, and each edge in 3DM becomes a "legal word" in UUL. $\endgroup$ – Gregory J. Puleo Nov 14 '14 at 3:32
  • $\begingroup$ So why do we need a 3DM instance? If we have a set (u,v,w) where u is in group X, v in group Y, and w in group Z, and edges (u, v) and (v,w), then u corresponds to a letter and (u,v) corresponds to a word starting with u, but what do v, w, and (v,w) represent? $\endgroup$ – Cortney Nov 14 '14 at 3:52
0
$\begingroup$

I think this is a good match for a multidimensional knapsack problem. There are 26 dimensions, one for each type of letter. The capacity of each dimension of the knapsack is the count of each available letter. The available objects to be placed in the knapsack correspond to words. The decision version of the problem applies ("Is there a collection of words that exactly uses up all the letters?").

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