Solving Superstring Exactly

Question

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).

Answer 1

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

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.

Answer 2

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; Karp; Bax, Franklin).

The best known approximation is $2\frac{11}{30}$ (Paluch).

The best known approximation of compression is $3\over4$ (Paluch).

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).

SCS cannot be approximated with a ratio better than $1.0029$ unless P=NP (Karpinski, Schmied).

Maximal Compression cannot be approximated with a ratio better than $1.0048$ unless P=NP (Karpinski, Schmied).

I would be grateful for any additions and suggestions.

Answer 3

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$.