Word tiling, where you must use each tile exactly once

Question

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.

Answer 1

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

Answer 2

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.