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?

  • $\begingroup$ @D.W. I am trying that. But I think Dynamic programming can at best give pseudo-polynomial time algorithm for the string version. $\endgroup$ Feb 22 '17 at 18:37
  • $\begingroup$ Could this be related to the bounded Post correspondence problem? Perhaps that is a possible reduction partner? In the bounded PCP, pairs can be used in any order and can be used multiple times, but cannot be swapped. $\endgroup$
    – D.W.
    Feb 22 '17 at 21:30
  • $\begingroup$ @D.W. it can be seen as a variant of PCP where we are given $n$ dominos and we ask wether we can flip some dominos so that the upper string is identical to the lower string (the order of dominos is fixed). $\endgroup$ Feb 22 '17 at 21:41
  • $\begingroup$ Personally I think this problem is solvable in polynomial time, but I haven't found a solution yet. Let $M$ denote the range (in even-odd partition)/maximum length (in this problem). In partition problem the input size is $O(n \log M)$, while in this problem it's $O(nM)$, so I believe this problem is easier. Here's a property which might be helpful: Suppose we concatenate the strings one by one, and we have already determined $b_1$ to $b_{i-1}$. Then both $b_i=0,1$ are valid only if one of $x_{i,1},x_{i,0}$ is a prefix of the other. $\endgroup$
    – aaaaajack
    Feb 23 '17 at 9:50
  • $\begingroup$ @D.W. if I am not mistaken, even-odd partition problem readily reduces to the string version when the alphabet is unary ( $\Sigma =\{ 1\}$). Therefore, the problem becomes wether the string version is NP-complete in the strong sense. $\endgroup$ Feb 23 '17 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.