Sam Buss and Michael Soltys
"Unshuffling a Square is NP-Hard"
Journal of Computer and Systems Sciences, 80, 4 (2014) 766-776.
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.
Back to Sam Buss's publications page.