Preprint:
Sam Buss and Michael Soltys
"Unshuffling a Square is NP-Hard"
Journal of Computer and Systems Sciences, 80, 4 (2014) 766-776.
DOI: 10.1016/j.jcss.2013.11.002
Download preprint version: PDF.
Abstract: A shuffle of two strings is formed by interleaving the characters into a new string, keeping the characters of each string in order. A string is a square if it is a shuffle of two identical strings. There is a known polynomial time dynamic programming algorithm to determine if a given string z is the shuffle of two given strings x, y; however, it has been an open question whether there is a polynomial time algorithm to determine if a given string z is a square. We resolve this by proving that this problem is NP-complete via a many-one reduction from 3-Partition.