MAXIMAL COMMON SUBSEQUENCES AND MINIMAL COMMON SUPERSEQUENCES

The problems of finding a longest common subsequence and a shortest co mmon supersequence of a set of strings are well known. They can be sol ved in polynomial time for two strings (in fact the problems are dual in this case), or for any fixed number of strings, by dynamic programm ing. But both problems are NP-hard in general for an arbitrary number k of strings. Here we study the related problems of finding a shortest maximal common subsequence and a longest minimal common supersequence . We describe dynamic programming algorithms for the case of two strin gs (for which case the problems are no longer dual), which can be exte nded to any fixed number of strings. We also show that both problems a re NP-hard in general for k strings, although the latter problem, unli ke shortest common supersequence, is solvable in polynomial time for s trings of length 2, Finally, we prove a strong negative approximabilit y result for the shortest maximal common subsequence problem. (C) 1996 Academic Press, Inc.