<p>Assuming the strings have length polynomial in $n$, then yes, there is at least a $2^{n-\Omega(\sqrt{n/\log n})}$ time solution. The reason is the well-known reduction from the shortest common superstring problem to ATSP with polynomial sized integer weights, which you in turn can solve by polynomial interpolation if you can count Hamiltonian cycles in a directed multigraph.
The latter problem has a $2^{n-\Omega(\sqrt{n/\log n})}$ time solution.
<a href="http://arxiv.org/abs/1211.0391">Björklund 2012</a></p>

<p>The reduction from ATSP with weights $w_{uv}$ for each pair of vertices $u,v$ to Hamiltonian cycle counting goes as follows:</p>

<p>For $r=1,2,\cdots,w_\mbox{sum}$, where $w_\mbox{sum}$ is an upper bound on all sums of $n$ weights in the ATSP instance, build one graph $G_r$ where you replace each weight $w_{uv}$ with $r^{w_{uv}}$ arcs from $u$ to $v$.</p>

<p>By solving the Hamiltonian cycle counting for each $G_r$, you can via polynomial interpolation construct a polynomial $\sum_{l=0}^{w_\mbox{sum}} a_lr^l$ with $a_l$ equal to the number of TSP tours in the original graph of weight $l$. Hence locating the smallest $l$ such that $a_l$ is non-zero solves the problem.</p>

CC BY-SA 3.0
2013-04-13T18:51:54.610Z
Thanks a lot! I didn't know this connection to the Hamiltonian cycle counting.
Alex Golovnev
CC BY-SA 3.0
2013-04-15T13:51:44.137Z
@AlexGolovnev: But the reduction is more-or-less the same as in e.g. the Kohn, Gottlieb, Kohn result you cited in your own answer? It is a simple embedding of the min-sum semiring on the integers. Anyhow, thank you for making me realize that the next version of my paper should state this explicitly.
Andreas Björklund
CC BY-SA 3.0
2013-04-13T06:25:57.450Z
2013-04-13T08:46:55.353Z
2013-04-13T08:46:55.353Z
Andreas Björklund
<p>I've studied the problem and I found some results.
Shortest Common Superstring (SCS) can be solved in time $2^n$ with only polynomial space(<a href="http://dl.acm.org/citation.cfm?id=810218" rel="nofollow">Kohn, Gottlieb, Kohn</a>; <a href="http://www.sciencedirect.com/science/article/pii/016763778290044X" rel="nofollow">Karp</a>; <a href="http://www.sciencedirect.com/science/article/pii/S0020019096001597" rel="nofollow">Bax, Franklin</a>).</p>

<p>The best known approximation is $2\frac{11}{30}$ (<a href="http://arxiv.org/pdf/1401.3670v1.pdf" rel="nofollow">Paluch</a>).</p>

<p>The best known approximation of compression is $3\over4$ (<a href="http://arxiv.org/pdf/1401.3670v1.pdf" rel="nofollow">Paluch</a>).</p>

<p>If SCS can be approximated by a factor $\alpha$ over the binary alphabet, then it can be approximated by a factor $\alpha$ over any alphabet (<a href="http://www.springerlink.com/content/9fcr047tk9xdv27n/" rel="nofollow">Vassilevska-Williams</a>).</p>

<p>SCS cannot be approximated with a ratio better than $1.0029$ unless P=NP (<a href="http://arxiv.org/abs/1111.5442" rel="nofollow">Karpinski, Schmied</a>).</p>

<p>Maximal Compression cannot be approximated with a ratio better than $1.0048$ unless P=NP (<a href="http://arxiv.org/abs/1111.5442" rel="nofollow">Karpinski, Schmied</a>).</p>

<p>I would be grateful for any additions and suggestions.</p>

CC BY-SA 3.0
2012-05-26T21:25:20.353Z
2014-01-18T12:40:23.963Z
2014-01-18T12:40:23.963Z
Alex Golovnev
<p>Here's the shortest superstring problem: you are given $n$ strings $s_1,\ldots, s_n$ over some alphabet $\Sigma$ and you want to find the shortest string over $\Sigma$ that contains each $s_i$ as a subsequence of consecutive characters, i.e. a substring.</p>

<p>When we talk about exact algorithms for the problem, finding the length $L$ of the shortest superstring is equivalent to finding the maximum compression $C$ which is the sum of all consecutive string overlaps in the final superstring, i.e. $C=\sum_i |s_i|-L$.</p>

<p>As far as I know, the fastest exact algorithm for shortest superstring runs in $O^*$($2^n$) where $n$ is the number of strings. This is a simple dynamic programming algorithm similar to the dynamic programming algorithm for longest path (and other problems): </p>

<p>For each subset of strings $S$ and string $v$ in $S$ we compute the maximum compression over all superstrings over $S$ where $v$ is the first string appearing in the superstring, storing this as C(($v,S$)). We do this by first processing all subsets with only one element, and then building up the C(($v,S$)) values for subsets $S$ on $k$ strings from those on $k-1$ strings. Specifically:</p>

<p>For each string $u$ we look at all subsets $S&#39;$ on $k-1$ strings that don't include $u$ and set the value for ($u,{u}\cup S'$) to the maximum over
strings $v$ in $S&#39;$ of the sum of the maximum overlap of $u$ with $v$ with C(($v,S'$)).</p>

<p>The final runtime is no more than O($n^2 2^n + n^2 l$) where $l$ is the maximum string length.</p>

<p>There are better algorithms if you assume that $l$ is small, or the pairwise overlaps are small, the alphabet size is small etc, but I am not aware of any algorithm that's faster than $2^n$.</p>

CC BY-SA 3.0
2012-01-06T19:31:39.473Z
OP knows $O^*(2^n)$ algorithm, he asked for faster solution.
Saeed
CC BY-SA 3.0
2012-01-07T02:10:03.307Z
as I said, I don't believe a faster solution is known.
virgi
CC BY-SA 3.0
2012-01-07T07:59:44.333Z
@virgi, thank you very much! Your algorithm is very nice. But I think inclusion-exclusion principle gives us even $O^*(2^n)$-algorithm with polynomial space for the Superstring problem. I'm really interesting in faster algorithms, may be with some constraints (small alphabet, short answer etc). Thank you very much!
Alex Golovnev
CC BY-SA 3.0
2012-01-06T19:25:11.683Z
2012-01-06T19:25:11.683Z
virgi
<p>What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?</p>

<p>UPD: 
$O^*(\cdot)$ suppresses polynomial factors.</p>

<p>The shortest superstring problem is a problem whose answer is the shortest string which contains each string from a given set of strings. 
The question is about optimization extension of a famous NP-hard problem Shortest Superstring(Garey and Johnson, p.228).</p>

CC BY-SA 3.0
2012-01-02T11:07:21.237Z
What is "the superstring problem"?
Jeffε
CC BY-SA 3.0
2012-01-02T11:14:05.567Z
I meant the Shortest Superstring Problem, I fixed it. Thank you!
Alex Golovnev
CC BY-SA 3.0
2012-01-02T12:46:03.570Z
Okay then, what's "the shortest superstring problem"?  I can think of several problems that deserve that name, and a few more that ought to be called "the shortest _supersequence_ problem" but probably aren't in practice.  Give us some context, please!
Jeffε
CC BY-SA 3.0
2012-01-02T15:54:09.207Z
Thanks! Sorry, I didn't know that this name can be interpreted differently. I updated the question.
Alex Golovnev
CC BY-SA 3.0
2012-01-06T19:36:17.967Z
What's your problem area? e.g if you looking for shortest super string in genome fragmentation, because genome fragmentation creates bounded tree width graphs, you can have fast algorithm, but if you just interested in faster than available algorithms, your answer is no, except you can have a faster algorithm in TSP (because of simple reduction), Also there is $O^*(2^{\sqrt n})$ algorithm in locally bounded tree width graphs.
Saeed
CC BY-SA 3.0
2012-01-07T08:06:57.190Z
@Saeed, Thank you very much! No, I didn't mean genome fragmentation. But I'm interesting in algorithms for bounded tree width graphs. Could you please give me a link? We can reduce Superstring to Asymmetric TSP. But I don't know a reduction from TSP to Superstring, which saves $n$. So I don't know a reason why the answer is no. For example, Bjorklund's algorithm gives us faster solution for symmetric TSP with bounded weights. After reduction to TSP, Superstring has bounded weights, but it is asymmetric version of TSP. So we can't use Bjorklund's algorithm.
Alex Golovnev
CC BY-SA 3.0
2012-01-07T08:55:30.883Z
@AlexGolovnev, Yes you are right this is ATSP, but for bounded treewidth I think is good to see http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 or if you want know more about them is good too see [algorithmic meta theorem](http://www.cs.ox.ac.uk/stephan.kreutzer/Publications/amt-survey.pdf)
Saeed
CC BY-SA 3.0
2012-01-10T21:26:05.403Z
@Saeed, Thank you for the link to algorithmic meta theorem. FPT  slides are very nice too. Before that I studied FPT slides by Fedor Fomin. Thanks!
Alex Golovnev
CC BY-SA 3.0
2012-01-11T11:25:40.503Z
@Saeed, It would be great, but unfortunately I can start only in late January. If you are interested, let's continue by e-mail? AlexGolovnev@gmail.com
Alex Golovnev
<cc.complexity-theory><ds.algorithms><graph-theory><tsp><exp-time-algorithms>
Solving Superstring Exactly
Alex Golovnev
# Solving Superstring Exactly

(Asked by: username_0 on 2012-01-02)

What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^\*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?

UPD:
$O^\*(\cdot)$ suppresses polynomial factors.

The shortest superstring problem is a problem whose answer is the shortest string which contains each string from a given set of strings.
The question is about optimization extension of a famous NP-hard problem Shortest Superstring(Garey and Johnson, p.228).

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, tsp, exp-time-algorithms
> **Comments:**
> **username_1**: What is "the superstring problem"?  
> **username_0**: I meant the Shortest Superstring Problem, I fixed it. Thank you!  
> **username_1**: Okay then, what's "the shortest superstring problem"?  I can think of several problems that deserve that name, and a few more that ought to be called "the shortest _supersequence_ problem" but probably aren't in practice.  Give us some context, please!  
> **username_0**: Thanks! Sorry, I didn't know that this name can be interpreted differently. I updated the question.  
> **username_2**: What's your problem area? e.g if you looking for shortest super string in genome fragmentation, because genome fragmentation creates bounded tree width graphs, you can have fast algorithm, but if you just interested in faster than available algorithms, your answer is no, except you can have a faster algorithm in TSP (because of simple reduction), Also there is $O^*(2^{\sqrt n})$ algorithm in locally bounded tree width graphs.  
> **username_0**: @Saeed, Thank you very much! No, I didn't mean genome fragmentation. But I'm interesting in algorithms for bounded tree width graphs. Could you please give me a link? We can reduce Superstring to Asymmetric TSP. But I don't know a reduction from TSP to Superstring, which saves $n$. So I don't know a reason why the answer is no. For example, Bjorklund's algorithm gives us faster solution for symmetric TSP with bounded weights. After reduction to TSP, Superstring has bounded weights, but it is asymmetric version of TSP. So we can't use Bjorklund's algorithm.  
> **username_2**: @AlexGolovnev, Yes you are right this is ATSP, but for bounded treewidth I think is good to see http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 or if you want know more about them is good too see [algorithmic meta theorem](http://www.cs.ox.ac.uk/stephan.kreutzer/Publications/amt-survey.pdf)  
> **username_0**: @Saeed, Thank you for the link to algorithmic meta theorem. FPT  slides are very nice too. Before that I studied FPT slides by Fedor Fomin. Thanks!  
> **username_0**: @Saeed, It would be great, but unfortunately I can start only in late January. If you are interested, let's continue by e-mail? AlexGolovnev@gmail.com  

---

## 3 answers

### Answer by username_3 on 2013-04-13. Score: 5 | Accepted answer

Assuming the strings have length polynomial in $n$, then yes, there is at least a $2^{n-\Omega(\sqrt{n/\log n})}$ time solution. The reason is the well-known reduction from the shortest common superstring problem to ATSP with polynomial sized integer weights, which you in turn can solve by polynomial interpolation if you can count Hamiltonian cycles in a directed multigraph.
The latter problem has a $2^{n-\Omega(\sqrt{n/\log n})}$ time solution.
[Björklund 2012](http://arxiv.org/abs/1211.0391)

The reduction from ATSP with weights $w\_{uv}$ for each pair of vertices $u,v$ to Hamiltonian cycle counting goes as follows:

For $r=1,2,\cdots,w\_\mbox{sum}$, where $w\_\mbox{sum}$ is an upper bound on all sums of $n$ weights in the ATSP instance, build one graph $G\_r$ where you replace each weight $w\_{uv}$ with $r^{w\_{uv}}$ arcs from $u$ to $v$.

By solving the Hamiltonian cycle counting for each $G\_r$, you can via polynomial interpolation construct a polynomial $\sum\_{l=0}^{w\_\mbox{sum}} a\_lr^l$ with $a\_l$ equal to the number of TSP tours in the original graph of weight $l$. Hence locating the smallest $l$ such that $a\_l$ is non-zero solves the problem.

> **Comments:**
> **username_0**: Thanks a lot! I didn't know this connection to the Hamiltonian cycle counting.  
> **username_3**: @AlexGolovnev: But the reduction is more-or-less the same as in e.g. the Kohn, Gottlieb, Kohn result you cited in your own answer? It is a simple embedding of the min-sum semiring on the integers. Anyhow, thank you for making me realize that the next version of my paper should state this explicitly.  

---

### Answer by username_0 on 2012-05-26. Score: 8

I've studied the problem and I found some results.
Shortest Common Superstring (SCS) can be solved in time $2^n$ with only polynomial space([Kohn, Gottlieb, Kohn](http://dl.acm.org/citation.cfm?id=810218); [Karp](http://www.sciencedirect.com/science/article/pii/016763778290044X); [Bax, Franklin](http://www.sciencedirect.com/science/article/pii/S0020019096001597)).

The best known approximation is $2\frac{11}{30}$ ([Paluch](http://arxiv.org/pdf/1401.3670v1.pdf)).

The best known approximation of compression is $3\over4$ ([Paluch](http://arxiv.org/pdf/1401.3670v1.pdf)).

If SCS can be approximated by a factor $\alpha$ over the binary alphabet, then it can be approximated by a factor $\alpha$ over any alphabet ([Vassilevska-Williams](http://www.springerlink.com/content/9fcr047tk9xdv27n/)).

SCS cannot be approximated with a ratio better than $1.0029$ unless P=NP ([Karpinski, Schmied](http://arxiv.org/abs/1111.5442)).

Maximal Compression cannot be approximated with a ratio better than $1.0048$ unless P=NP ([Karpinski, Schmied](http://arxiv.org/abs/1111.5442)).

I would be grateful for any additions and suggestions.


---

### Answer by username_4 on 2012-01-06. Score: 5

Here's the shortest superstring problem: you are given $n$ strings $s\_1,\ldots, s\_n$ over some alphabet $\Sigma$ and you want to find the shortest string over $\Sigma$ that contains each $s\_i$ as a subsequence of consecutive characters, i.e. a substring.

When we talk about exact algorithms for the problem, finding the length $L$ of the shortest superstring is equivalent to finding the maximum compression $C$ which is the sum of all consecutive string overlaps in the final superstring, i.e. $C=\sum\_i |s\_i|-L$.

As far as I know, the fastest exact algorithm for shortest superstring runs in $O^\*$($2^n$) where $n$ is the number of strings. This is a simple dynamic programming algorithm similar to the dynamic programming algorithm for longest path (and other problems):

For each subset of strings $S$ and string $v$ in $S$ we compute the maximum compression over all superstrings over $S$ where $v$ is the first string appearing in the superstring, storing this as C(($v,S$)). We do this by first processing all subsets with only one element, and then building up the C(($v,S$)) values for subsets $S$ on $k$ strings from those on $k-1$ strings. Specifically:

For each string $u$ we look at all subsets $S'$ on $k-1$ strings that don't include $u$ and set the value for ($u,{u}\cup S'$) to the maximum over
strings $v$ in $S'$ of the sum of the maximum overlap of $u$ with $v$ with C(($v,S'$)).

The final runtime is no more than O($n^2 2^n + n^2 l$) where $l$ is the maximum string length.

There are better algorithms if you assume that $l$ is small, or the pairwise overlaps are small, the alphabet size is small etc, but I am not aware of any algorithm that's faster than $2^n$.

> **Comments:**
> **username_2**: OP knows $O^*(2^n)$ algorithm, he asked for faster solution.  
> **username_4**: as I said, I don't believe a faster solution is known.  
> **username_0**: @virgi, thank you very much! Your algorithm is very nice. But I think inclusion-exclusion principle gives us even $O^*(2^n)$-algorithm with polynomial space for the Superstring problem. I'm really interesting in faster algorithms, may be with some constraints (small alphabet, short answer etc). Thank you very much!  

---

