View source for Shortest common supersequence problem

In [[Computer science|computer science]], the '''shortest common supersequence''' of two sequences '''X''' and '''Y''' is the shortest sequence which has '''X''' and '''Y''' as [[Subsequence|subsequence]]s. This is a problem closely related to the [[Longest common subsequence problem|longest common subsequence problem]]. Given two sequences '''X''' = < x<sub>1</sub>,...,x<sub>m</sub> > and '''Y''' = < y<sub>1</sub>,...,y<sub>n</sub> >, a sequence '''U''' = < u<sub>1</sub>,...,u<sub>k</sub> > is a common supersequence of '''X''' and '''Y''' if items can be removed from '''U''' to produce '''X''' and '''Y'''.
A shortest common supersequence (SCS) is a common supersequence of minimal length.  In the shortest common supersequence problem, two sequences '''X''' and '''Y''' are given, and the task is to find a shortest possible common supersequence of these sequences.  In general, an SCS is not unique.

For two input sequences, an SCS can be formed from a [[Longest common subsequence|longest common subsequence]] (LCS) easily.  For example, the longest common subsequence of '''X'''<math>[1..m] = abcbdab</math> and '''Y'''<math>[1..n] = bdcaba</math> is '''Z'''<math>[1..L] = bcba</math>.  By inserting the non-LCS symbols into '''Z''' while preserving their original order, we obtain a shortest common supersequence '''U'''<math>[1..S] = abdcabdab</math>.  In particular, the equation <math>L + S = m + n</math> holds for any two input sequences.

There is no similar relationship between shortest common supersequences and longest common subsequences of three or more input sequences.  (In particular, LCS and SCS are not dual problems.)  However, both problems can be solved in <math>O(n^k)</math> time using dynamic programming, where <math>k</math> is the number of sequences, and <math>n</math> is their maximum length.  For the general case of an arbitrary number of input sequences, the problem is NP-hard.<ref>{{cite journal| author = David Maier| title = The Complexity of Some Problems on Subsequences and Supersequences| journal = J. ACM| volume = 25| year = 1978| pages = 322&ndash;336| doi = 10.1145/322063.322075| publisher = ACM Press| issue = 2| s2cid = 16120634| doi-access = free}}</ref>

== Shortest common superstring ==

The closely related problem of finding a minimum-length string which is a superstring of a finite set of strings {{var|S}} = { {{var|s}}<sub>1</sub>,{{var|s}}<sub>2</sub>,...,{{var|s}}<sub>n</sub> } is also NP-hard.<ref>{{cite journal 
 |title=The shortest common supersequence problem over binary alphabet is NP-complete
 |author=Kari-Jouko Räihä, Esko Ukkonen
 |journal=Theoretical Computer Science
 |volume=16
 |number=2
 |date=1981
 |pages=187–198
 |doi=10.1016/0304-3975(81)90075-x
 |doi-access=free
 }}</ref>  Several constant factor approximations have been proposed throughout the years, and the current best known algorithm has an approximation factor of 2.475.<ref>{{cite journal
|title=Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
|author=Matthias Englert and Nicolaos Matsakis and Pavel Vesel
|journal=Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
|date=2022
|pages=317–330
|doi=10.1145/3519935.3520001
|isbn=9781450392648
|s2cid=243847650
|url=https://dl.acm.org/doi/10.1145/3519935.3520001
}}
</ref> However, perhaps the simplest solution is to reformulate the problem as an instance of [[Set cover problem#Weighted set cover|weighted set cover]] in such a way that the weight of the optimal solution to the set cover instance is less than twice the length of the shortest superstring {{var|S}}. One can then use the [[Approximation algorithm#Performance guarantees|O(log({{var|n}}))-approximation]] for weighted set-cover to obtain an O(log({{var|n}}))-approximation for the shortest superstring (note that this is ''not'' a constant factor approximation).

For any string {{var|x}} in this alphabet, define {{var|P}}({{var|x}}) to be the set of all strings which are substrings of {{var|x}}. The instance {{var|I}} of set cover is formulated as follows: 
* Let {{var|M}} be empty.
* For each pair of strings {{var|s}}<sub>{{var|i}}</sub> and {{var|s}}<sub>{{var|j}}</sub>, if the last {{var|k}} symbols of {{var|s}}<sub>{{var|i}}</sub> are the same as the first {{var|k}} symbols of {{var|s}}<sub>{{var|j}}</sub>, then add a string to {{var|M}} that consists of the concatenation with maximal overlap of {{var|s}}<sub>{{var|i}}</sub> with {{var|s}}<sub>{{var|j}}</sub>. 
* Define the universe <math>\mathcal U</math> of the set cover instance to be {{var|S}}
* Define the set of subsets of the universe to be { {{var|P}}({{var|x}}) | {{var|x}} ∈ {{var|S}} ∪ {{var|M}} }
* Define the cost of each subset {{var|P}}(x) to be |{{var|x}}|, the length of {{var|x}}.

The instance {{var|I}} can then be solved using an algorithm for weighted set cover, and the algorithm can output an arbitrary concatenation of the strings {{var|x}} for which the weighted set cover algorithm outputs {{var|P}}({{var|x}}).{{sfn|Vazirani|p=20}}

=== Example ===

Consider the set {{var|S}} = { abc, cde, fab }, which becomes the universe of the weighted set cover instance. In this case, {{var|M}} = { abcde, fabc }. Then the set of subsets of the universe is
:<math displaystyle="block">
\begin{align}
  \{ P(x) | x\in S\cup M \} 
  &= \{ P(x) | x\in \{ abc, cde, fab, abcde, fabc \} \} \\
  &= \{ P(abc), P(cde), P(fab), P(abcde), P(fabc) \} \} \\
  &= \{ \{a,b,c,ab,bc,abc\}, \{c,d,e,cd,de,cde\},\ldots, \{f,a,b,c,fa,ab,bc,fab,abc,fabc\} \} \} \\
\end{align}
</math>
which have costs 3, 3, 3, 5, and 4, respectively.

== References ==
{{Reflist}}

* {{cite book | first1=Michael R. | last1=Garey |  first2=David S. | last2=Johnson |  year=1979 | title=Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher=W.H. Freeman | isbn=0-7167-1045-5 | zbl=0411.68039 | at=[https://archive.org/details/computersintract0000gare/page/ p. 228 A4.2: SR8] | title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}
* {{cite book | last=Szpankowski | first=Wojciech |  title=Average case analysis of algorithms on sequences | others=With a foreword by Philippe Flajolet | series=Wiley-Interscience Series in Discrete Mathematics and Optimization | location=Chichester | publisher=Wiley | year=2001 | isbn=0-471-24063-X | zbl=0968.68205 }}
* {{Citation| last = Vazirani | first = Vijay V.
 | title = Approximation Algorithms
 | year = 2001
 | publisher = Springer-Verlag
 | isbn = 3-540-65367-8
 | url = http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pd
 }}

==External links==
* [http://nist.gov/dads/HTML/shortestCommonSuperseq.html Dictionary of Algorithms and Data Structures: shortest common supersequence]

[[Category:Combinatorics]]
[[Category:Formal languages]]
[[Category:Dynamic programming]]
[[Category:NP-complete problems]]
[[Category:Approximation algorithms]]

{{Sourceattribution|Shortest common supersequence problem|1}}