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