The Complexity of Some Problems on Subsequences and Supersequences
David Maier · Journal of the ACM · 1978
The complexity of finding the Longest Common Subsequence (LCS) and the Shortest Common Supersequence (SCS) of an arbRrary number of sequences IS considered We show that the yes/no version of the LCS problem is NP-complete for sequences over an alphabet of size 2, and that the yes/no SCS problem is NPcomplete for sequences over an alphabet of size 5 KEY WORDS AND PHRASES computational complexity, NP-completeness, longest common subsequence, shortest common supersequence CR CATEGORIES 5 23, 5 39 DefinitionsGiven a finite sequence S = sl, s2, ..., sin, we define a subsequence S' of S to be any sequence which consists of S with between 0 and m terms deleted (e.g.ac, ad, and abcd are all subsequences of abcd).We write S' S'.Given a set R = {$1, $2 ..... Sp} of sequences, we speak of a Longest Common Subsequence of R, LCS(R), as a longest sequence S such that S S,, I = 1 ..... p.For example, SCS({abbb, bab, bba} ) = abbab.The yes~no LCS (SCS)problem is: Given an integer k and a listing of the sequences in R, is ILCS(R)[ --> k (ISCS(R)I .~k), where IsI is the number of terms in sequence S?Whenever we refer to the LCS and SCS problems in this paper, we will mean the yes/no versions.We define the alphabet of R, X(R), to be the finite set of values the terms of sequences S1, $2 ..... Sp take on.Clearly IX(R) I -< ml + m2 + + rap, where m, = [ S,I.We also use I I to denote the cardinality of a set; the context will distinguish the usage. Threading SchemesIt is convenient to think of the LCS and SCS problems in terms of threading beads.We think of a sequence as a row of beads and the matching process as threading the beads m a certain manner.Suppose we have three sequences $1 = bybrr, $2 --yyrrbr, and $3 = byrry.We represent them as rows of beads:General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit hbrarles acting for them provided that ACM's copyright noUce is given and that reference is made to the pubhcatlon, to ItS date of msue, and to the fact that reprinting prlwleges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does repubhcatlon, or systematic or muluple reproduction