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).
Solving Superstring Exactly
cc.complexity theory;ds.algorithms;graph theory;tsp;exp time algorithms
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.Bjrklund 2012The 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.