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

### SHORTEST COMMON SUPERSEQUENCE

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

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

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

- Good News: Approximable within (|R|+3)4 [156].

- Bad News: Not in APX [260].

- Comment: Transformation from MINIMUM FEEDBACK VERTEX SET and self-improvability. Not approximable within for some unless NP [260]. APX-complete if the size of the alphabet is fixed [260] and [82]. Variation in which the objective is to find the longest minimal common supersequence (a supersequence that cannot be reduced to a shorter common supersequence by removing a letter) is APX-hard even over the binary alphabet, and SHORTEST MAXIMAL COMMON NON-SUPERSEQUENCE is APX-hard even over the binary alphabet [356]. Variation in which the longest common subsequence is known is also APX-hard even over the binary alphabet [123].

- Garey and Johnson: SR8

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