5
$\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$
4
  • $\begingroup$ How about unary? $\endgroup$
    – KWillets
    Jun 11, 2017 at 18:36
  • $\begingroup$ @KWillets If the strings are in unary, then a simple dynamic programming approach works in polynomial time. $\endgroup$ Jun 14, 2017 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, 2017 at 18:03
  • $\begingroup$ @RB No. Your version of partition appears to be hard. $\endgroup$ Jun 29, 2017 at 5:24

1 Answer 1

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
  • 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$ Sep 5, 2017 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$ Sep 7, 2017 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.