Return to Answer

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.

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.

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 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.

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.

Here is a relatively simpler $NP$-completeness proof for finding non-nested Perfect Matching in a graph. The journal article by Li and Li, On two open problems of 2-interval patterns proves that Maximum 2-interval pattern problem under model $R=\{<, \between\}$ ( abbreviated as DIS-2-IP-$\{<, \between\}$ problem) is $NP$-hard. This problem is equivalent to your problem of finding non-nested Perfect Matching (they use bioinformatics terminology to describe the problem). The crucial link is that a set of 2-intervals over disjoint support intervals corresponds to the edges of a graph with linear order on its vertices.

The equivalence between the two problems is clearly stated in page ten of this reference, New results for the 2-interval pattern problem, by Blin, Fertin, and Vialette. In this paper, they refer to the problem as 2-IP-DIS-$\{<, \between\}$ problem.

The footnote in page ten (page 320 of the published proceedings) of the pre-print of second reference, the authors state that:

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.

Basically, what they are saying in the footnote is that any two edges $\{u,v\}$ and $\{ u', v' \}$ in the maximum matching ($M$) are non-nested under the linear ordering $\pi$ of the vertices.

EDIT: This paper, On Recognizing Words That Are Squares for the Shuffle Product , authored by Rizzi and Vialette, gives a direct and simple proof of the $NP$-completeness of unshuffling a string. They state that the complexity of unshuffling a binary string is still open.

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 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.