Next: MAXIMUM COMMON SUBTREE Up: Compression and Representation Previous: SHORTEST COMMON SUPERSTRING Index

### LONGEST COMMON SUBSEQUENCE

- INSTANCE: Finite alphabet , finite set R of strings from .

- SOLUTION: A string such that w is a subsequence of each , i.e. one can get w by taking away letters from each x.

- MEASURE: Length of the subsequence, i.e., |w|.

- Good News: Approximable within , where m is the length of the shortest string in R [210].

- Bad News: Not approximable within for any , where n is the maximum of |R| and [71], [260] and [63].

- Comment: Transformation from MAXIMUM INDEPENDENT SET. APX-complete if the size of the alphabet is fixed [260] and [82]. Variation in which the objective is to find the shortest maximal common subsequence (a subsequence that cannot be extended to a longer common subsequence) is not approximable within for any [157].

- Garey and Johnson: SR10