×

Longest subsequences in permutations. (English) Zbl 1040.68064

Let \(X\) be a class of permutations. \(X\) is called closed if whenever \(\sigma\in X\) and \(\pi\leq\sigma\), then \(n\in X\), where \(\pi\leq\sigma\) means that \(\pi\) is a subpermutation of \(\sigma\) (or \(\pi\) occurs as a pattern within \(\sigma\)), i.e. there is a subsequence of a whose members appear in the same relative order as the elements of \(\pi\) (the subsequence of \(\sigma\) is said to be isomorphic to \(\pi\)). For a fixed (eventually closed) set \(X\) of permutations, the longest \(X\)-subsequence (L\(X\)S) problem is defined as follows: Is there an efficient algorithm to find, for any given permutation \(\sigma\), a longest subpermutation of \(\sigma\)? If \(I\) is the set of identity permutations of all lengths, one obtains the L\(I\)S problem, a much better known problem of computing the longest increasing subsequence of a sequence of values (and a special case of the L\(X\)S problem).
The aim of the present paper is to investigate the L\(X\)S problem using the simpler L\(I\)S problem, for a number of closed sets \(X\) for which there exist polynomial-time algorithms. While the L\(I\)S problem has algorithms of run-time complexity \(O(n\log n)\), the general L\(X\)S problem is known to be NP-hard. The authors develop a construction that defines a large number of closed sets for which the L\(X\)S problem has polynomial time algorithms. These closed sets for which L\(X\)S problem runs in polynomial time can be defined by avoiding a certain set of permutations of length 3. Along with the description of the polynomial approach to the L\(X\)S problem, other closely related interesting open problems and the large area of applications (e.g. aligning whole genomes) are outlined.

MSC:

68R05 Combinatorics in computer science
92D20 Protein sequences, DNA sequences
05A05 Permutations, words, matrices
PDFBibTeX XMLCite