# 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