Shortest common supersequence

<h2 id="shortest-common-superstring">Shortest common superstring</h2>
<p>The closely related problem of finding a minimum-length string which is a superstring of a finite set of strings S = { s1,s2,...,sn } is also NP-hard.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>  Several constant factor approximations have been proposed throughout the years, and the current best known algorithm has an approximation factor of 2.475.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> However, perhaps the simplest solution is to reformulate the problem as an instance of <a href="/facts/Set_cover_problem/MVzyBYs1">weighted set cover</a> 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 S. One can then use the <a href="/facts/Approximation_algorithm/BWlf7M32">O(log(n))-approximation</a> for weighted set-cover to obtain an O(log(n))-approximation for the shortest superstring (note that this is <i>not</i> a constant factor approximation).
</p><p>For any string x in this alphabet, define P(x) to be the set of all strings which are substrings of x. The instance I of set cover is formulated as follows: 
</p>
<ul><li>Let M be empty.</li>
<li>For each pair of strings si and sj, if the last k symbols of si are the same as the first k symbols of sj, then add a string to M that consists of the concatenation with maximal overlap of si with sj.</li>
<li>Define the universe 
  
    
      
        
          
            U
          
        
      
    
    {\displaystyle {\mathcal {U}}}
  
 of the set cover instance to be S</li>
<li>Define the set of subsets of the universe to be { P(x) | x ∈ S ∪ M }</li>
<li>Define the cost of each subset P(x) to be |x|, the length of x.</li></ul>
<p>The instance I can then be solved using an algorithm for weighted set cover, and the algorithm can output an arbitrary concatenation of the strings x for which the weighted set cover algorithm outputs P(x).<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h3>Example</h3>
<p>Consider the set S = { abc, cde, fab }, which becomes the universe of the weighted set cover instance. In this case, M = { abcde, fabc }. Then the set of subsets of the universe is
</p>

{
                P
                (
                x
                )
                
                  |
                
                x
                ∈
                S
                ∪
                M
                }
              
              
                
                =
                {
                P
                (
                x
                )
                
                  |
                
                x
                ∈
                {
                a
                b
                c
                ,
                c
                d
                e
                ,
                f
                a
                b
                ,
                a
                b
                c
                d
                e
                ,
                f
                a
                b
                c
                }
                }
              
            
            
              
              
                
                =
                {
                P
                (
                a
                b
                c
                )
                ,
                P
                (
                c
                d
                e
                )
                ,
                P
                (
                f
                a
                b
                )
                ,
                P
                (
                a
                b
                c
                d
                e
                )
                ,
                P
                (
                f
                a
                b
                c
                )
                }
                }
              
            
            
              
              
                
                =
                {
                {
                a
                ,
                b
                ,
                c
                ,
                a
                b
                ,
                b
                c
                ,
                a
                b
                c
                }
                ,
                {
                c
                ,
                d
                ,
                e
                ,
                c
                d
                ,
                d
                e
                ,
                c
                d
                e
                }
                ,
                …
                ,
                {
                f
                ,
                a
                ,
                b
                ,
                c
                ,
                f
                a
                ,
                a
                b
                ,
                b
                c
                ,
                f
                a
                b
                ,
                a
                b
                c
                ,
                f
                a
                b
                c
                }
                }
                }
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}\{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{aligned}}}

<p>which have costs 3, 3, 3, 5, and 4, respectively.
</p>

<ul><li><a href="/facts/Michael_R._Garey/xuSLYs90">Garey, Michael R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, David S.</a> (1979). <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss"><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i></a>. W.H. Freeman. <a href="https://archive.org/details/computersintract0000gare/page/">p. 228 A4.2: SR8</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-7167-1045-5. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0411.68039">0411.68039</a>.</li>
<li><a href="/facts/Wojciech_Szpankowski/hfopodEp">Szpankowski, Wojciech</a> (2001). <i>Average case analysis of algorithms on sequences</i>. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-24063-X. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0968.68205">0968.68205</a>.</li>
<li><a href="/facts/Vijay_Vazirani/QzVR2f9n">Vazirani, Vijay V.</a> (2001), <a href="http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pd"><i>Approximation Algorithms</i></a>, Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-65367-8</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://nist.gov/dads/HTML/shortestCommonSuperseq.html">Dictionary of Algorithms and Data Structures: shortest common supersequence</a></li>
<li><a href="https://www.geeksforgeeks.org/shortest-common-supersequence/">Shortest Common Supersequence</a></li>
<li><a href="https://leetcode.com/problems/shortest-common-supersequence/">1092. Shortest Common Supersequence</a></li>
<li><a href="https://www.codingninjas.com/studio/problem-details/shortest-supersequence_4244493">Shortest Common Supersequence</a></li>
<li><a href="https://algorithm-visualizer.org/dynamic-programming/shortest-common-supersequence">Shortest common supersequence</a></li>
<li><a href="https://p-library.com/o/scs/">Shortest Common Supersequence (SCS)</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>David Maier (1978). "The Complexity of Some Problems on Subsequences and Supersequences". J. ACM. 25 (2). ACM Press: 322–336. doi:10.1145/322063.322075. S2CID 16120634. <a href="https://doi.org/10.1145%2F322063.322075" target="_blank">https://doi.org/10.1145%2F322063.322075</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Kari-Jouko Räihä, Esko Ukkonen (1981). "The shortest common supersequence problem over binary alphabet is NP-complete". Theoretical Computer Science. 16 (2): 187–198. doi:10.1016/0304-3975(81)90075-x. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Matthias Englert and Nicolaos Matsakis and Pavel Vesel (2022). "Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios". Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (PDF). pp. 317–330. doi:10.1145/3519935.3520001. ISBN 9781450392648. S2CID 243847650. <a href="9781450392648" target="_blank">9781450392648</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Vazirani 2001, p. 20. - Vazirani, Vijay V. (2001), Approximation Algorithms, Springer-Verlag, ISBN 3-540-65367-8 <a href="http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pd" target="_blank">http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pd</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Shortest common supersequence open-in-new

Shortest common supersequence