Dokładne rozwiązywanie superstrun

Co wiadomo o dokładnej złożoności najkrótszego problemu superstrun? Czy można to rozwiązać szybciej niż $O^*(2^n)$ ? Czy znane są algorytmy, które rozwiązują najkrótszy superstrun bez redukcji do TSP?

UPD: $O^*(\cdot)$ tłumi czynniki wielomianowe.

Najkrótszy problem superstrun to problem, którego odpowiedzią jest najkrótszy ciąg, który zawiera każdy ciąg z danego zestawu ciągów. Pytanie dotyczy rozszerzenia optymalizacji znanego problemu NP-Short Shortest Superstring (Garey i Johnson, str. 228).

Zakładając, że łańcuchy mają długość wielomianową w , wtedy tak, jest co najmniej 2 n - Ω ( $n$rozwiązanie czasowe. Powodem jest dobrze znana redukcja z najkrótszego najczęstszego problemu superstrunu do ATSP z wielomianowymi wagami liczb całkowitych, które z kolei można rozwiązać przez interpolację wielomianową, jeśli można policzyć cykle Hamiltona w ukierunkowanej multigrafii. Ten ostatni problem ma2n-Ω($2^{n-\Omega(\sqrt{n/\log n})}$rozwiązanie czasowe. Björklund 2012$2^{n-\Omega(\sqrt{n/\log n})}$

Redukcję z ATSP z wagą dla każdej pary wierzchołków kształcie U , V do Hamiltona zliczania cykli jest następujący:$w_{uv}$$u,v$

Dla , w którym w sumie stanowi górne ograniczenie wszystkich sumy n wag w przypadku ATSP, budować jeden wykres G r gdzie zastąpić każdą wagę w u , v w r W U v łuków z u do v .$r=1,2,\cdots,w_\mbox{sum}$$w_\mbox{sum}$$n$$G_r$$w_{uv}$$r^{w_{uv}}$$u$$v$

Rozwiązując liczenie cykli hamiltonowskich dla każdego , można za pomocą interpolacji wielomianowej skonstruować wielomian ∑ w suma l = 0 a l r l o wartości l równej liczbie tras TSP na oryginalnym wykresie wagi l . Dlatego też umieszczenie najmniejszą l tak, że L nie jest równa zeru rozwiązuje problemu.$G_r$$\sum_{l=0}^{w_\mbox{sum}} a_lr^l$$a_l$$l$$l$$a_l$

Studiowałem problem i znalazłem kilka wyników. Najkrótszy wspólny superstrun (SCS) można rozwiązać w czasie tylko przestrzenią wielomianową ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ).$2^n$

Najbardziej znanym przybliżeniem jest (Paluch).$2\frac{11}{30}$

Najbardziej znanym przybliżeniem kompresji jest (Paluch).$3\over4$

Jeśli SCS można aproksymować współczynnikiem stosunku do binarnego alfabetu, to można go aproksymować współczynnikiem α w stosunku do dowolnego alfabetu ( Vassilevska-Williams ).$\alpha$$\alpha$

SCS nie może być aproksymowany współczynnikiem lepszym niż chyba że P = NP ( Karpinski, Schmied ).$1.0029$

Maksymalnej kompresji nie można aproksymować współczynnikiem lepszym niż chyba że P = NP ( Karpinski, Schmied ).$1.0048$

Byłbym wdzięczny za wszelkie uzupełnienia i sugestie.

Oto najkrótsza problemem superstrun: dostaniesz ciągów s 1 , ... , y n nad jakimś alfabetu Ď i chcesz znaleźć najkrótszą ciąg nad Ď który zawiera każdy s I jako podciąg kolejnych znaków, czyli podciąg.$n$$s_1,\ldots, s_n$$\Sigma$$\Sigma$$s_i$

$L$$C$$C=\sum_i |s_i|-L$

$O^*$$2^n$$n$

$S$$v$$S$$S$$v$$v,S$$v,S$$S$$k$$k-1$

Dla każdego ciągu $u$ patrzymy na wszystkie podzbiory $S'$ na $k-1$ ciągi, które nie obejmują $u$ i ustaw wartość dla ($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$.