4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How about unary? $\endgroup$ – KWillets Jun 11 '17 at 18:36
  • $\begingroup$ @KWillets If the strings are in unary, then a simple dynamic programming approach works in polynomial time. $\endgroup$ – Mikhail Rudoy Jun 14 '17 at 7:12
  • $\begingroup$ Do you know the answer for "classic" partition where you simply have a string set $S$ and you want a partition $S_1,S_2$ and an order on $S_1$ and $S_2$ such that the concatenation of $S_1$ equals the concatenation of $S_2$? It might be easier to reduce to this, and if the "classic" problem is not hard, neither is yours. $\endgroup$ – R B Jun 26 '17 at 18:03
  • $\begingroup$ @RB No. Your version of partition appears to be hard. $\endgroup$ – Mohammad Al-Turkistany Jun 29 '17 at 5:24
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Also the case in which we don't allow the $\epsilon$ seems interesting (the strings are from $\{0,1\}^+$) ... I don't see a quick fix for the reduction for this case. $\endgroup$ – Marzio De Biasi Sep 5 '17 at 7:25
  • $\begingroup$ While the wording of the problem allows empty strings, the interesting cases (as pointed out by Marzio) occur when both $x_{i, 0}$ and $x_{i, 1}$ are not equal to $\epsilon$. $\endgroup$ – Mohammad Al-Turkistany Sep 7 '17 at 12:53

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.