# Word tiling, where you must use each tile exactly once

Given words $$w_1,\ldots,w_n$$ in binary alphabet and another word $$w$$, decide if $$w$$ can be written as a product $$w = w_{i_1} \cdots w_{i_n}$$ (in the monoid $$\{0,1\}^\ast$$) for some permutation of indices.

Is this a known problem? Is it NP-complete?

Details:

1. The words $$w_1,\dots,w_n$$ are part of the input. Therefore, there is no a priori upper bound on $$n$$, $$|w_i|$$, or $$|w|$$. However, we may assume that $$|w|=\sum |w_i|$$.

2. If we restrict the problem to instances with $$|w_i|\le k$$ (where $$k$$ is a fixed constant), we obtain a new problem $$WT_k$$. $$WT_k$$ belongs to $$P$$. It's possible to build a polynomial-time algorithm for $$WT_k$$, using dynamic programming. Indeed, in this case the number of different words $$w_i$$ is bounded by $$2^k$$. Hence any sequence $$\{w_1,\ldots,w_n\}$$ can be encoded by a $$2^k$$-tuple of integers (an element of $$\mathbb{Z}^{2^k}$$). It is convenient to assume that $$w_i\ne \varepsilon$$.

Now with every initial segment $$w'$$ of $$w$$ we associate a set of tuples in $$\mathbb{Z}^{2^k}$$ that describe sequences of $$w_i$$'s resulting in $$w'$$. For instance, with $$\varepsilon$$ we associate a single tuple $$(0,\ldots,0)$$ and $$\varepsilon$$ is considered processed. Then for every processed segment $$w'$$ we go over its tuples and see which ones we can append to $$w'$$ (which $$w_i$$'s are still available). For instance, if $$w' w_i$$ gives another initial segment $$w''$$ of $$w$$ then we add the corresponding tuple for $$w''$$. Eventually, all initial segments will be covered. Here it is crucial that $$k$$ is fixed, as it ensures that the sets of tuples associated with every $$w'$$ is polynomially bounded (with a very large degree).

3. I suspect that the general problem is NP-complete and I'd appreciate any suggestions.

4. Clearly the problem can be viewed as a sort of a bounded Post correspondence problem with a fixed collection of pairs $$(w,\varepsilon),(\varepsilon,w_1),\ldots,(\varepsilon,w_n)$$. Not sure if this helps, though.

5. Clearly, the restriction to a binary alphabet is irrelevant. One can work with any countable alphabet. Need to be careful though: the item 2 does not hold when the alphabet is unbounded.

• The PCP-problem here is confusing rather than helpful. In PCP one may reuse the pairs (or even omit some). Moreover PCP is tied to undecidablity? – Hendrik Jan Oct 13 '14 at 0:21
• Have you looked at shuffle languages? – Pseudonym Oct 13 '14 at 1:58
• No, I know nothing about shuffle languages. The name sounds very promising. I will look into that. If you have more information, please share. – user59343 Oct 13 '14 at 13:15
• Ok, I found this paper: users.soe.ucsc.edu/~manfred/pubs/J1.pdf which claims a very similar result "The following problem is NP-complete. Given $w,w_1,\ldots,w_n$ decide if $w$ is in the shuffle of $w_1,\ldots,w_n$". I just do not completely understand the definition of shuffle on page 347 and the real meaning of Theorem 3.1. I will try to get through the proof I guess. – user59343 Oct 13 '14 at 14:02
• No, unfortunately, shuffle operator allows to cut through $w_i$'s. So the results by A. Mansfield, M. Warmuth, D. Haussler are not applicable in a direct way. Links: "On the computational complexity of a merge recognition problem" by A. Mansfield in Discrete Applied Mathematics and "On the complexity of iterated shuffle" by M. Warmuth, D. Haussler, in Journal of Computer and System sciences. – user59343 Oct 13 '14 at 14:38

I can't speak to whether it's a known problem, but it is NP-complete.

It's clearly in NP, so we just have to show NP-hardness. The following reduction is from the strongly NP-hard 3-partition problem, which asks, given a multiset of positive integers $[x_1,\ldots,x_{3m}]$, whether there exists a partition into $m$ submultisets such that the sum of each submultiset is equal to the integer $s=\frac{1}{m}\sum_{i=1}^{3m}x_i$. For each $i\in\{1,\ldots,3m\}$, make a string $a^{x_i}$. Make $m-1$ strings $b$. The target word $w$ is

$$a^sba^sb\cdots ba^s.$$

• The 3-partition problem additionally requires that each submultiset have exactly 3 integers in it. I don't understand how your reduction enforces that. Am I missing something? – D.W. Aug 13 '18 at 22:28
• @D.W. I should say, the 3-partition problem where all numbers are in the range (s/4, s/2), which per Wikipedia is still hard. – David Eisenstat Aug 13 '18 at 23:41

The problem is NP-complete. This can also be done very simply with sub-set sum:

Given a set of numbers $$x_1, x_2, ... x_n$$ that sums to $$s$$ and a number $$k$$. For each number $$x_i$$, make 2 words $$a^{x_i}$$ and $$b^{x_i}$$. The word $$w$$ is $$a^{k}b^{k}a^{s-k}b^{s-k}$$

• If there is a subset that sums to $$k$$, then we can construct the word $$w$$ by using the corresponding $$a^{x_i}$$'s to build the first part of the word $$w$$.

The corresponding $$b^{x_i}$$'s are used to build the second part of $$w$$. All other words are used to form the other part of $$w$$

• If there is permutation that forms $$w$$, then we look at the first part that contains just $$a$$ see which words form that part. And then we take their corresponding numbers from the original subset to form the subset that sums to $$k$$.

The transformation is in poly-time. For the length of the transformed input, we can encode each word with just a pair of character and number to avoid too long input.

• Unfortunately, this reduction takes exponential time. The word $w$ has length at least $k$, which is exponentially large, as the size of the input is $\lg k$. Therefore, this does not appear to be a valid proof of NP-completeness. – D.W. Aug 13 '18 at 22:29