Recognizing binary shuffle squares is NP-hard

A shuffle of two words is formed by interleaving the characters into a new word, keeping the characters of each word in order. A word is a shuffle square if it is a shuffle of two identical words. Deciding whether a word is a shuffle square has been proved to be NP-complete independently by Buss and Soltys [5] and Rizzi and Vialette [20], the former proving the result for alphabets as small as 9 letters. We prove in this paper that deciding whether a binary word is a shuffle square is NP-complete.

Authors

• Laurent Bulteau
• Stéphane Vialette

Keywords

• Strings
• Shuffle product
• Binary alphabets
• NP-hardness