Longest subsequences in permutations.
Michael Albert, Robert E. L. Aldred, Michael Atkinson, Hans P. van Ditmarsch, B. D. Handley, Chris C. Handley, Jaroslav Opatrný · Australas. J Comb. · 2003
For a class of permutationsX the LXS problem is to identify in a given permutation σ of length n its longest subsequence that is isomorphic to a permutation of X. In general LXS is NP-hard. A general construction that produces polynomial time algorithms for many classes X is given. More efficient algorithms are given when X is defined by avoiding some set of permutations of length 3.