ON THE APPROXIMATION OF LONGEST COMMON NONSUPERSEQUENCES AND SHORTEST COMMON NONSUBSEQUENCES

摘要

The longest common nonsupersequence (LCNS) problem is shown to be NP-complete over the binary alphabet, and Max SNP-hard, in general. Although it is open whether this problem and the shortest common nonsubsequence problem are Max SNP-hard over the binary alphabet, we show that their generalizations (the mixed supersequence and the mixed subsequence problems) indeed remain Max SNP-hard over the binary alphabet. [References: 13]