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

Additional Metadata
Keywords Algorithms, Computational complexity, Pattern matching, Permutation, Separable permutation
Journal Information Processing Letters
Citation
Bose, P, Buss, J.F. (Jonathan F.), & Lubiw, A. (Anna). (1998). Pattern matching for permutations. Information Processing Letters, 65(5), 277–283.