Memecahkan Superstring Tepat

Apa yang diketahui tentang kompleksitas tepat dari masalah superstring terpendek? Bisakah itu diselesaikan lebih cepat dari ? Apakah ada algoritma yang dikenal yang memecahkan superstring terpendek tanpa mengurangi menjadi TSP? $O^*(2^n)$

UPD: menekan faktor polinomial. $O^*(\cdot)$

Masalah superstring terpendek adalah masalah yang jawabannya adalah string terpendek yang berisi setiap string dari serangkaian string yang diberikan. Pertanyaannya adalah tentang perluasan optimasi dari masalah NP-hard Shortest Superstring yang terkenal (Garey dan Johnson, hal.228).

cc.complexity-theory ds.algorithms graph-theory tsp exp-time-algorithms Alex Golovnev
sumber

Apa itu "masalah superstring"?

Jeff

Maksud saya Masalah Superstring Terpendek, saya memperbaikinya. Terima kasih!

Alex Golovnev

Baiklah kalau begitu, apa "masalah superstring terpendek"? Saya dapat memikirkan beberapa masalah yang pantas untuk nama itu, dan beberapa lagi yang seharusnya disebut " masalah supersequence terpendek " tetapi mungkin tidak dalam praktiknya. Tolong beri kami beberapa konteks!

Jeff

Apa masalah Anda? misalnya jika Anda mencari string super terpendek dalam fragmentasi genom, karena fragmentasi genom membuat grafik lebar pohon terbatas, Anda dapat memiliki algoritma cepat, tetapi jika Anda hanya tertarik pada algoritma yang lebih cepat daripada yang tersedia, jawaban Anda adalah tidak, kecuali Anda dapat memiliki algoritma yang lebih cepat dalam TSP (karena reduksi sederhana), Juga ada algoritma dalam grafik lebar pohon yang dibatasi secara lokal.

O^{*} (2^{\sqrt{n}})

$O^*(2^{\sqrt n})$

Saeed

@AlexGolovnev, Ya Anda benar ini adalah ATSP, tetapi untuk treewidth terbatas saya pikir baik untuk melihat cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 atau jika Anda ingin tahu lebih banyak tentang mereka juga melihat algoritmik meta theorem

Saeed

Jawaban:

Dengan asumsi string memiliki polinomial panjang dalam , maka ya, setidaknya ada solusi waktu . Alasannya adalah pengurangan terkenal dari masalah superstring umum terpendek ke ATSP dengan bobot bilangan bulat polinomial, yang pada gilirannya dapat Anda selesaikan dengan interpolasi polinomial jika Anda dapat menghitung siklus Hamiltonian dalam multigraf diarahkan. Masalah terakhir memiliki solusi waktu . Björklund 2012 $n$ $2^{n-\Omega(\sqrt{n/\log n})}$ $2^{n-\Omega(\sqrt{n/\log n})}$

Pengurangan dari ATSP dengan bobot untuk setiap pasangan simpul ke penghitungan siklus Hamilton terjadi sebagai berikut: $w_{uv}$ $u,v$

Untuk , di mana adalah batas atas pada semua jumlah bobot dalam contoh ATSP, buat satu grafik mana Anda mengganti setiap bobot dengan busur dari ke . $r=1,2,\cdots,w_\mbox{sum}$ $w_\mbox{sum}$ $n$ $G_r$ $w_{uv}$ $r^{w_{uv}}$ $u$ $v$

Dengan menyelesaikan penghitungan siklus Hamilton untuk setiap , Anda dapat melalui interpolasi polinomial membangun polinomial dengan sama dengan jumlah tur TSP dalam grafik asli berat . Oleh karena itu menemukan terkecil sehingga adalah non-nol menyelesaikan masalah. $G_r$ $\sum_{l=0}^{w_\mbox{sum}} a_lr^l$ $a_l$ $l$ $l$ $a_l$

Andreas Björklund
sumber

Terima kasih banyak! Saya tidak tahu hubungan ini dengan penghitungan siklus Hamilton.

Alex Golovnev

@AlexGolovnev: Tapi pengurangannya kurang lebih sama dengan di misalnya hasil Kohn, Gottlieb, Kohn yang Anda kutip dalam jawaban Anda sendiri? Ini adalah penyederhanaan sederhana dari penjumlahan min-sum pada bilangan bulat. Bagaimanapun, terima kasih telah membuat saya menyadari bahwa versi berikutnya dari makalah saya harus menyatakan ini secara eksplisit.

Andreas Björklund

Saya telah mempelajari masalahnya dan saya menemukan beberapa hasil. Shortest Common Superstring (SCS) dapat diselesaikan dalam waktu dengan hanya ruang polinomial ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ). $2^n$

Perkiraan yang paling dikenal adalah ( Paluch ). $2\frac{11}{30}$

$3\over4$

$\alpha$ $\alpha$

$1.0029$

$1.0048$

Saya akan berterima kasih atas penambahan dan saran.

Alex Golovnev
sumber

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

virgi
sumber

O^{*} (2^{n})

$O^*(2^n)$

seperti yang saya katakan, saya tidak percaya solusi yang lebih cepat diketahui.

virgi

O^{*} (2^{n})

$O^*(2^n)$