String version of even-odd partition problem

Question

Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version.

String even-odd partition

INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e., $n$ pairs of strings over $\{0,1\}^*$

QUESTION: Does there exist $(b_1,\dots,b_n) \in \{0,1\}^n$ such that $x_{1,b_1} \cdots x_{n,b_n} = x_{1,1-b_1} \cdots x_{n,1-b_n}$?

Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.

Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W_{even} $ and $W_{odd}$ such that $W_{even}= W_{odd}$, where exactly one string from each pair goes to $W_{even}$ and the other goes to $W_{odd}$. The selected strings have to stay in the same order they appear in the input.

It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.

Is there a simple reduction to prove the NP-completeness of this string variant?

This was posted first on CS StackExchange.

Answer 1

It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see this question for references and discussion.

Here, for two strings $u$ and $v$ the shuffle product is defined as the set of all $w = u_1 v_1 \ldots u_i v_i$ for each representation $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_k$ with $u_i, v_i \in \Sigma^*$ (i.e. $u_i$ and $v_i$ are strings, not letters).

The reduction is easy: given $w = a_1 \ldots a_n$, $a_i \in \Sigma$, take $x_{i, 0} = a_i$ and $x_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.

Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.