How can I convert a list with duplicates into a set for a reduction to the set cover problem?

Question

I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here.

Here's a condensed version of the problem:
You're given a collection of refrigerator magnet letters that may contain duplicates. You have a limited vocabulary of words made of combinations of those letters (again, a word may contain the same letter twice). Can you choose words from the vocabulary to build with the magnets such that all of the magnets are used and each magnet is used in only one word?

It's suspiciously similar to the set cover problem, so I've been trying to come up with a way to convert (in polynomial time) a collection of symbols that potentially contains duplicates into a set. This would allow the collection of symbols to be used as U and the child's vocabulary to be used as S for set cover.

I've had no luck so far, so a hint or even a suggestion for a more appropriate NP-complete problem to reduce to would be greatly appreciated.

Answer 1

There are several possible interpretations of the problem:

1. The alphabet size could be fixed or unbounded.
2. Words could be repeated or not.
3. The input histogram (how many letters of each type) could be encoded in unary (e.g., the letters are "aabcccccc") or in binary (e.g. $a\times 2, b\times 1, c \times 4$).

Here is the complexity of some of these variants.

Fixed alphabet, words may not be repeated, histogram is encoded in unary. Use dynamic programming. Given the list of words $w_1,\ldots,w_n$, compute inductively all possible histograms of all possible subsets of $w_1,\ldots,w_i$ which are "within budget". If the budget is $b_1,\ldots,b_m$ (so the alphabet size is $m$), then the number of such histograms is at most $(b_1+1)\cdots(b_m+1) \leq (2\max b_j)^m$, which is polynomial in the input size. Check whether the budget is one of these possible histograms.

Fixed alphabet, words may be repeated, histogram is encoded in unary. A similar strategy works, using a fixpoint iteration. Maintain a list of reachable histogram. At each round, add all words to all reachable histograms under budget, and update the list. Stop when the list stabilizes. Check whether the input histogram is one of them.

Unbounded alphabet. NP-complete, by reduction from 1-in-3 SAT. There is one letter per variable and clause, and one word per variable truth assignment. The word contains the variable symbol as well as the clauses satisfied by the assignment. All budgets are $1$.