Common Permutation Problem

In this paper we show that the following problem is NP-complete: Given an alphabet $\mathrm{\Sigma }$ and two strings over $\mathrm{\Sigma }$, the question is whether there exists a permutation of $\mathrm{\Sigma }$ which is a subsequence of both of the given strings.