1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the alphabet size fixed? $\endgroup$ – Yuval Filmus Aug 2 '15 at 20:53
  • $\begingroup$ Can a vocabulary word be used more than once? $\endgroup$ – Yuval Filmus Aug 2 '15 at 20:55
  • $\begingroup$ How is the input given? $\endgroup$ – Yuval Filmus Aug 2 '15 at 20:56
  • $\begingroup$ @YuvalFilmus I believe the alphabet size is fixed. A word can be used more than once. I didn't think about that before; it could be another issue for the reduction since that isn't allowed in the set cover problem. The input is given as described in the problem--a collection of symbols and a "vocabulary"--I interpret that as a set of strings over said collection of symbols. For the full problem text see the link in my question. EDIT: I reread the problem description and it explicitly says words can be used more than once. $\endgroup$ – jzimbel Aug 2 '15 at 21:00
  • 1
    $\begingroup$ You should supply all relevant data in the question body. I'm not going to read the link. $\endgroup$ – Yuval Filmus Aug 2 '15 at 21:01
1
$\begingroup$

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

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