Using up letters on a refrigerator is NP-complete

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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?").