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 can be done in time O(n log log n) [CW].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
Series Lecture Notes in Computer Science
Citation
Bose, P, Buss, J.F. (Jonathan F.), & Lubiw, A. (Anna). (1993). Pattern matching for permutations. In Lecture Notes in Computer Science.