18
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ What is "the superstring problem"? $\endgroup$ – Jeffε Jan 2 '12 at 11:07
  • $\begingroup$ I meant the Shortest Superstring Problem, I fixed it. Thank you! $\endgroup$ – Alex Golovnev Jan 2 '12 at 11:14
  • 10
    $\begingroup$ 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! $\endgroup$ – Jeffε Jan 2 '12 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Saeed Jan 6 '12 at 19:36
  • 1
    $\begingroup$ @AlexGolovnev, Yes you are right this is ATSP, but for bounded treewidth I think is good to see cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 or if you want know more about them is good too see algorithmic meta theorem $\endgroup$ – Saeed Jan 7 '12 at 8:55
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! I didn't know this connection to the Hamiltonian cycle counting. $\endgroup$ – Alex Golovnev Apr 13 '13 at 18:51
  • $\begingroup$ @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. $\endgroup$ – Andreas Björklund Apr 15 '13 at 13:51
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ OP knows $O^*(2^n)$ algorithm, he asked for faster solution. $\endgroup$ – Saeed Jan 6 '12 at 19:31
  • 2
    $\begingroup$ as I said, I don't believe a faster solution is known. $\endgroup$ – virgi Jan 7 '12 at 2:10
  • 1
    $\begingroup$ @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! $\endgroup$ – Alex Golovnev Jan 7 '12 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.