PATTERN-MATCHING FOR PERMUTATIONS

Given a permutation T of 1 to n, and a permutation P of 1 to k, for k less than or equal to 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 cor responding counting problem, in the case that P is separable - i.e., c ontains neither the subpattern (3, 1,4, 2) nor its reverse, the subpat tem (2,4, 1,3). (C) 1998 Published by Elsevier Science B.V.