Given a permutation T of 1 to n, and a permutation P of 1 to k, for k ≤ n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is (1,2,..., k), then we wish to find an increasing subsequence of length k in T; this special case was done in time O(n log log n) by Chang and Wang. We prove that the general problem is NP-complete. We give a polynomial time algorithm for the decision problem, and the corresponding counting problem, in the case that P is separable - i.e., contains neither the subpattern (3,1,4,2) nor its reverse, the subpattern (2,4,1,3).

Algorithms, Computational complexity, Pattern matching, Permutation, Separable permutation
Information Processing Letters
School of Computer Science

Bose, P, Buss, J.F. (Jonathan F.), & Lubiw, A. (Anna). (1998). Pattern matching for permutations. Information Processing Letters, 65(5), 277–283.