- 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., .

*Good News:*Approximable within [169].*Bad News:*Not in APX [275].*Comment:*Transformation from MINIMUM FEEDBACK VERTEX SET and self-improvability. Not approximable within for some unless NPQP [275]. APX-complete if the size of the alphabet is fixed [275] and [89]. 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 [376]. Variation in which the longest common subsequence is known is also APX-hard even over the binary alphabet [133].*Garey and Johnson:*SR8