How hard is unshuffling a string? 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.
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