Resolução de supercordas exatamente

O que se sabe sobre a complexidade exata do menor problema de supercorda? Pode ser resolvido mais rapidamente que ? Existem algoritmos conhecidos que resolvem as supercordas mais curtas sem reduzir ao TSP?$O^*(2^n)$

UPD: suprime fatores polinomiais.$O^*(\cdot)$

O menor problema de supercorda é um problema cuja resposta é a menor string que contém cada string de um determinado conjunto de strings. A questão é sobre a extensão da otimização de um famoso problema difícil de NP, Shortest Superstring (Garey e Johnson, p.228).

Assumindo que as seqüências tenham polinômio de comprimento em , sim, há pelo menos 2 n - Ω ( $n$solução de tempo. O motivo é a conhecida redução do menor problema comum de supercorda para o ATSP com pesos inteiros de tamanho polinomial, que você pode resolver por interpolação polinomial se puder contar os ciclos hamiltonianos em um multigráfico direcionado. O último problema tem2n-Ω($2^{n-\Omega(\sqrt{n/\log n})}$solução de tempo. Björklund 2012$2^{n-\Omega(\sqrt{n/\log n})}$

A redução do ATSP com pesos para cada par de vértices u , v para a contagem do ciclo hamiltoniano é a seguinte:$w_{uv}$$u,v$

Para , onde w soma é um limite superior de todas as somas de n pesos no exemplo ATSP, construir um gráfico G r , onde pode substituir cada peso w u v com r w u v arcos de u para v .$r=1,2,\cdots,w_\mbox{sum}$$w_\mbox{sum}$$n$$G_r$$w_{uv}$$r^{w_{uv}}$$u$$v$

Ao resolver o ciclo de contagem Hamiltoniano para cada , pode por meio de interpolação polinomial construir um polinómio Σ w soma L = 0 um l r l com um L igual ao número de passeios de TSP no grafo original de peso l . Daí localizar o menor l de tal forma que um L é diferente de zero resolve o problema.$G_r$$\sum_{l=0}^{w_\mbox{sum}} a_lr^l$$a_l$$l$$l$$a_l$

Estudei o problema e encontrei alguns resultados. A supercorda comum mais curta (SCS) pode ser resolvida no tempo com apenas espaço polinomial ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ).$2^n$

A aproximação mais conhecida é (Paluch).$2\frac{11}{30}$

A aproximação mais conhecida da compressão é (Paluch).$3\over4$

Se o SCS puder ser aproximado por um fator sobre o alfabeto binário, poderá ser aproximado por um fator α sobre qualquer alfabeto ( Vassilevska-Williams ).$\alpha$$\alpha$

$1.0029$

$1.0048$

Ficaria muito grato por quaisquer adições e sugestões.

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

$u$$S'$$k-1$$u$$u,{u}\cup S'$$v$$S'$$u$$v$$v,S'$

$n^2 2^n + n^2 l$$l$

$l$$2^n$