How hard is unshuffling a string?

Question

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.

Is there a fast algorithm to determine whether a string is square, or is it NP-hard? The obvious dynamic programming approach doesn't seem to work.

Even the following special cases appear to be hard: (1) strings in which each character appears at most four six times, and (2) strings with only two distinct characters. As Per Austrin points out below, the special case where each character occurs at most four times can be reduced to 2SAT.

---

Update: This problem has another formulation that may make a hardness proof easier.

Consider a graph G whose vertices are the integers 1 through n; identify each edge with the real interval between its endpoints. We say that two edges of G are nested if one interval properly contains the other. For example, the edges (1,5) and (2,3) are nested, but (1,3) and (5,6) are not, and (1,5) and (2,8) are not. A matching in G is non-nested if no pair of edges is nested. Is there a fast algorithm to determine whether G has a non-nested perfect matching, or is that problem NP-hard?

• Unshuffling a string is equivalent to finding a non-nested perfect matching in a disjoint union of cliques (with edges between equal characters). In particular, unshuffling a binary string is equivalent to finding a non-nested perfect matching in a disjoint union of two cliques. But I don't even know if this problem is hard for general graphs, or easy for any interesting classes of graphs.

• There is an easy polynomial-time algorithm to find perfect non-crossing matchings.

---

Update (Jun 24, 2013): The problem is solved! There are now two independent proofs that identifying square strings is NP-complete.

• In November 2012, Sam Buss and Michael Soltys announced a reduction from 3-partition, which shows that the problem is hard even for strings over a 9-character alphabet. See "Unshuffling a Square is NP-Hard", Journal of Computer System Sciences 2014.

• In June 2013, Romeo Rizzi and Stéphane Vialette published a reduction from the longest common subsequence problem. See "On Recognizing Words That Are Squares for the Shuffle Product", Proc. 8th International Computer Science Symposium in Russia, Springer LNCS 7913, pp. 235–245.

There is also a simpler proof that finding non-nested perfect matchings is NP-hard, due to Shuai Cheng Li and Ming Li in 2009. See "On two open problems of 2-interval patterns", Theoretical Computer Science 410(24–25):2410–2423, 2009.

Answer 1

Michael Soltys and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only $7$ distinct symbols, although our proof is written for an alphabet with $9$ symbols. This question is still open for smaller alphabets, say with only $2$ symbols. We have not looked at the problem under the restriction that each symbol appears only $6$ times (or, more generally, a constant number of times); so that question is still open.

The proof uses a reduction from $3$-Partition. It is too long to post here, but a preprint, "Unshuffling a string is $\text{NP}$-hard", is available from our web pages at:

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

and

http://www.cas.mcmaster.ca/~soltys/#Papers.

The paper has been published in the Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Answer 2

For the special case you mention when each character appears at most four times, there is a simple reduction to 2-SAT (unless I'm missing something...), as follows:

The crucial point is that for each character, there are (at most) two valid ways of matching the occurrences of the character (the third possibility will be nesting). Use a boolean variable to represent which of the two matchings is chosen. Now an assignment to these variables gives a valid unshuffle of the string iff for every pair of edges that are nested, not both were chosen. This condition can be precisely described by a disjunction of the variables (possibly negated) corresponding to the two characters involved.

Answer 3

Here is an algorithm that may have some chance of being correct though it seems tricky to prove and I would not bet the house on it...

Let us say that $G$ is purged if for every edge $e$, there exists a (possibly nested) perfect matching of $G$ that uses $e$ and does not use any edge contained in or containing $e$.

It is easy to test if $G$ is purged and if not to find the violating edges. Clearly none of these violating edges can be used in a non-nesting perfect matching of $G$, so it is safe to remove them from consideration. Repeating this process, we obtain a (unique) purged subgraph of $G$ which has a non-nested perfect matching iff $G$ has.

Now comes the leap of faith, which may or may not be correct: the hope is that in a purged graph, if there are still vertices of degree $> 1$, we can do the greedy choice and match the first such vertex to its first neighbor (or equivalently, remove the edges to all its other neighbors).

After the greedy choice we purge the graph again, and so on, and the process ends when the graph is (hopefully) a non-nesting perfect matching.

At first I thought this would be roughly like having a small look-ahead in the greedy algorithm and not really work, but I found it surprisingly difficult to come up with a counterexample.

Answer 4

The solution that Sam Buss and I proposed in November 2012 (showing that unshuffling a square in NP-hard by a reduction from 3-Partition) is now a published article in the Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Answer 5

Romeo Rizzi and Stéphane Vialette prove that recognizing square strings is NP-complete in their 2013 paper "On Recognizing Words That Are Squares for the Shuffle Product", by reduction from the longest binary subsequence problem. They state that the complexity of unshuffling a binary strings is still open.

An even simpler proof that finding non-nested perfect matching is NP-complete is given by Shuai Cheng Li and Ming Li in their 2009 paper "On two open problems of 2-interval patterns". However, they use terminology inherited from bioinformatics. Instead of "perfect non-nested matching", they call it the "DIS-2-IP-$\{<, \between\}$ problem". The equivalence between the two problems is described by Blin, Fertin, and Vialette:

The 2-IP-DIS-$\{<, \between\}$ problem has an immediate formulation in terms of constrained matchings in general graphs: Given a graph $G$ together with a linear ordering $\pi$ of the vertices of $G$, the 2-IP-DIS-$\{<, \between\}$ problem is equivalent to finding a maximum cardinality matching $M$ in $G$ with the property that for any two distinct edges $\{u, v\} $ and $\{u', v'\}$ of $M$ neither $min \{ \pi(u), \pi(v) \} \lt min \{ \pi(u'), \pi(v') \} $ and $max \{ \pi(u'), \pi(v') \lt max \{ \pi(u), \pi(v) \} $ nor $min \{ \pi(u'), \pi(v') \} \lt min \{ \pi(u), \pi(v) \}$ and $max \{ \pi(u), \pi(v) \} \lt max \{ \pi(u'), \pi(v') \}$ occur.

Update (February 25, 2019): Bulteau and Vialette showed that the decision problem of unshuffling a binary string is NP-complete in their paper, Recognizing binary shuffle squares is NP-hard.

Answer 6

Does this help?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Answer 7

NEVER MIND, THIS ANSWER IS WRONG. It fails on input "AABAAB": greedily matching the first two A's with each other makes it impossible to match the remaining symbols. I'm leaving it up rather than deleting it to help others avoid making the same mistake.

It seems to me that it's always safe to match each successive character of the supposed square greedily to another equal character that is in as early a position as possible. That is, I think the following linear time algorithm should work:

Loop through each position i in the input string, i = 0, 1, 2, ... n. For each position i, check whether that position has already been matched against some earlier position in the string. If not, match it against an equal character that comes after the last already matched position and is otherwise as early as possible in the string. If a match is not found for some character, declare that the input is not a square; otherwise, it is the set of characters in the first pair of each match.

Here it is in Python:

def sqrt(S):
    matches = []
    i, j = 0, 0
    while i < len(S):
        if j < len(matches) and matches[j][1] == i:
            i += 1
            j += 1
            continue
        if matches:
            k = matches[-1][1] + 1
        else:
            k = 1
        while k < len(S) and S[k] != S[i]:
            k += 1
        if k >= len(S):
            raise Exception("Not a square")
        matches.append((i,k))
        i += 1
    return "".join(S[a] for a,b in matches)

print sqrt("ABCABDCD")

Here i is the main loop variable (the position we're trying to match), j is a pointer into the array of matched pairs that speeds up the check of whether position i is already matched, and k is an index used to search for the character that matches the one at position i. It's linear time because i, j, and k are monotonically increasing through the string and each inner loop iteration increases one of them.

Answer 8

Update: It doesn't make sense to talk about the difficulty of finding perfect matching that is non-nesting and non-crossing, when the labels are from 1 to n, because there is only one such. (Yes, am kicking myself.) However, it would make sense given a larger range on the labels... so I still see some hope, but it might be quite pointless after all. I would certainly have to follow this up some more.

---

I can think of why it might be hard to find a matching that is non-nesting and non-crossing. Let me call such a matching a disjoint matching. Not sure to what extent this helps, but let me present the reasoning anyway. (I should point out that my argument, as it stands here, is not complete, and the detail I leave out is possibly crucial. However, I imagine that it might be something of a start.)

I'll begin with a slightly different problem. Given a graph $G$ whose edges are colored with $k$ colors, and the vertices are labeled from $1$ to $n$, is there a disjoint matching that contains exactly one edge of each color? This problem appears to be NP-hard (the argument for this is both complete and straightforward - unless I am missing something). The reduction spews out a graph that is a disjoint union of cliques.

The reduction is from Disjoint Factors, a NP-complete problem introduced in [1]. An instance of disjoint factors is given by a string over an alphabet of size $k$, and the question is whether there are $k$ disjoint factors, where a factor is a substring that begins and ends with the same letter; and two factors are disjoint if they don't overlap in the string (note that 'nesting', in particular, is disallowed too).

Let me denote by $a_1,\ldots, a_k$, the elements of the $k$-sized alphabet associated with the Disjoint Factors instance.

Given an instance of disjoint factors, that is, say a string of length $n$, create a graph that has $n$ vertices with vertex labels from $1$ to $n$. Add an edge between vertices $u$ and $v$ if the corresponding positions have the same letter (say $a_i$), and also color the edge $(u,v)$ with color $i$.

The proof of the reduction essentially follows from the definitions. Given $k$ disjoint factors, we clearly have a $k$-disjoint colorful matching, merely pick the edges as given by the disjoint factors, and it is easy to see that the resulting matching is both colorful and disjoint. Conversely, if there is a $k$-disjoint colorful matching, then we have k disjoint factors, one for every letter, because the matching is colorful (and hence picks one factor per letter), and is disjoint (so the corresponding factors would not overlap).

To get rid of the colors and make the matching perfect, albeit on a possibly larger range, make the following modifications to the graph thus created:

Let $U_a$ denote the subset of vertices that have labels which are positions associated with the letter $a$. If $U_a$ has $A$ vertices, then add $(A-2)$ new vertices and induce a complete bipartite graph between $U_a$ and the newly added vertices. Repeat, of course, for every letter.

Roughly speaking, if the graph is to induce a perfect matching, the newly introduced vertices must be matched with the vertices of $U_a$, and they will saturate all but a pair of vertices, and the edge between the remaining vertices will correspond to the disjoint factor. I have not worked out the numbers that one must associate with the newly added vertices... note that they must be so that the resulting matching is disjoint. I just have a feeling (read: hope) that it 'can be done'!

[1] On problems without polynomial kernels, Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows and Danny Hermelin, J. Comput. Syst. Sci.

Answer 9

The approach doesn't work: decomposing a shuffled square by taking out two matching letters does not result into shuffled squares... See Radu's comments below.

---

A proposal using Range Concatenation Grammars (RCGs, see http://hal.inria.fr/inria-00073347/en/): I'm was under the impression that the following simple RCG recognizes your "shuffled squares" language over a finite alphabet $\Sigma$, EDITED after Radu's first comment: $${\small \begin{aligned} S(XY)&\Rightarrow A(X,Y)&(1)\newline A(aX_1, aX_2Y_1Y_2)&\Rightarrow A(X_1,Y_1)\,A(X_2,Y_2)&(2)\newline A(\varepsilon,\varepsilon)&\Rightarrow\varepsilon&(3) \end{aligned}} $$ where $a$ ranges over $\Sigma$ and $\varepsilon$ denotes the empty string.

The grammar checks with the second predicate that it matches a letter from the first word occurrence with the same letter in the second word occurrence. It then guesses how to match the remainder of the remaining first word letters, i.e. $X_1$ with a substring of the remainder, namely $Y_1$. Everything before $Y_1$ therefore belongs to the first word instance; we call it $X_2$ and we guess that it matches some suffix starting at $Y_2$. Note that $Y_1$ and $Y_2$ might contain letters from both instances of the word, but $X_1$ and $X_2$ only contain letters from the first instance.

For example, here is a possible derivation of your string $abcabdcd$: $${\small\begin{aligned} S(abcabdcd) &\Rightarrow A(abc, abdcd) &(\text{by } 1, X=abc, Y=abdcd)\newline &\Rightarrow A(bc,bdcd)\,A(\varepsilon,\varepsilon)&(\text{by } 2, X_1=bc, Y_1=bdcd, X_2=Y_2=\varepsilon)\newline &\Rightarrow A(c,c)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow^3\varepsilon&\text{i.e. success} \end{aligned}}$$

For $0011$, $${\small\begin{aligned} S(0011)&\Rightarrow A(0,011)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(1,1)\newline &\Rightarrow A(1,1)\newline &\Rightarrow^\ast \varepsilon \end{aligned}}$$

Now, Boullier shows in the previously linked paper that there is a dynamic programming polynomial time algorithm for RCGs, which answers your question if the above grammar is were correct. The idea is that, although I presented above the instanciations of variables $X$, $Y$, etc. as strings, they really are intervals inside the input string, which can be properly tabulated.

Answer 10

Update: As Tsuyoshi Ito points out in the comments, this algorithm has exponential running time.

Original post:

Here is how I would program this in the Real World.

We are given a string S = (S[1],...,S[n]). For each prefix S_r = (S[1],...,S[r]), there is a set {(T_i, U_i)} of pairs of strings, such that S_r is a shuffle of (T_i, U_i), and T_i is a prefix of U_i (i.e. U_i 'starts with' T_i). S_r itself is a square if and only if this set contains a pair (T_i, U_i) with T_i = U_i.

Now, we don't need to generate all of these pairs; we just need to generate the suffix V_i of each string U_i obtained by removing its copy of T_i. This will eliminate a (possibly exponential) number of irrelevant duplicates. Now S_r is a square if and only if this set of suffixes contains the empty string. So the algorithm becomes:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

For instance, if S is AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

We can discard all suffixes that are more than half as long as the input string, so this simplifies to:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

I have programmed this in C++, and it works on all the examples given here. I can post the code, if anybody's interested. The question is: can the size of SuffixSet grow faster than polynomially?

Answer 11

EDIT: This is an incorrect answer.

---

Sylvain suggested an RCG which unfortunately was not appropriate for these "shuffle squares". However, I think there is one (EDIT: not an RCG, see Kurt's comments below!), which looks as follows:

$\begin{aligned} S(Y) & \rightarrow A(\epsilon,Y) & (1) \newline A(X, ZY) & \rightarrow A(XZ,Y) & (2) \newline A(aX, aY) & \rightarrow A(X,Y) \quad \text{ for every } a \in \Sigma & (3) \newline A(\epsilon,\epsilon) & \rightarrow \epsilon & (4) \end{aligned}$

Explanation: recall that we have to match symbols which can appear anywhere in the string, but once we have matched $a$ and $a'$, we can only match $b$ and $b'$ if $a \prec b$ implies $a' \prec b'$ ($\prec$ meaning linear precedence). The idea is that we split the string $(1,2)$ in order to compare prefixes of the halves. If the beginnings of two substrings match, we can reduce the problem to the remaining strings $(3)$. If not, we can transfer some part of the right hand side to the left hand side $(2)$ and see if there is a match at a later position. What's important is that this is only allowed in one direction!

Here's a derivation for $100110101010$ (a counterexample to Sylvain's RCG):

$\begin{aligned} S(100110101010) & \Rightarrow A(\epsilon,100110101010) & (1) \newline & \Rightarrow A(1001,10101010) & (2) \newline & \Rightarrow^* A(01,101010) & (3) \newline & \Rightarrow A(011,01010) & (2) \newline & \Rightarrow^* A(1,010) & (3) \newline & \Rightarrow A(10,10) & (2) \newline & \Rightarrow^* A(\epsilon, \epsilon) & (3) \newline & \Rightarrow \epsilon & (4) \end{aligned}$

I haven't worked out a formal proof that this grammar indeed captures exactly the "shuffle squares" but it should not be too hard. Sylvain already mentioned that the decision problem for RCGs is polynomial.