Common Permutation Problem
Marián Dvorský · arXiv (Cornell University) · 2008
In this paper we show that the following problem is NP-complete: Given an alphabet $Σ$ and two strings over $Σ$, the question is whether there exists a permutation of $Σ$ which is a subsequence of both of the given strings.