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

*Good News:*Approximable within , where*m*is the length of the shortest string in*R*[223].*Bad News:*Not approximable within for any , where*n*is the maximum of and [77], [275] and [68].*Comment:*Transformation from MAXIMUM INDEPENDENT SET. APX-complete if the size of the alphabet is fixed [275] and [89]. 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 [170].*Garey and Johnson:*SR10