Masalah grafik yang sulit dipecahkan secara sub-responsif

25

Mengingat hasil terbaru dari Arora, Barak, dan Steurer, Algoritma Subeksponensial untuk Game Unik dan Masalah Terkait , saya tertarik pada masalah grafik yang memiliki algoritma waktu subeksponensial tetapi diyakini tidak dapat dipecahkan secara polinomial. Contoh terkenal adalah grafik isomorfisme yang memiliki algoritma subeksponensial run-time. Contoh lain adalah masalah log-Clique yang dapat dipecahkan dalam waktu kuasi polinomial ( ). $2^{O(n^{1/2} \log n)}$ $n^{O(\log n)}$

Saya mencari contoh menarik dan lebih disukai referensi untuk survei masalah grafik keras subeksponensial (belum tentu lengkap). Juga, Apakah ada masalah grafik lengkap dengan algoritma waktu subexponential? $NP$ $NP$

Impagliazzo, Paturi dan Zane menunjukkan bahwa Hipotesis Eksponensial Waktu menyiratkan bahwa Clique, k-Colorability, dan Vertex Cover perlu waktu. $2^{\Omega(n)}$

cc.complexity-theory reference-request Mohammad Al-Turkistany
sumber

2

Hanya untuk kelengkapan: log-CLIQUE =

{(G, k) | G has n vertices, k = \log n and G has a clique of size k}

$\{(G, k) | G \text{ has }n\text{ vertices, }k = \log n\text{ and }G\text{ has a clique of size }k\}$

MS Dousti

20

Ngomong-ngomong masalah Max Clique, secara umum penuh, dapat diselesaikan dalam waktu mana adalah ukuran input. $2^{\tilde O(\sqrt N)}$ $N$

Ini sepele jika grafik direpresentasikan melalui matriks adjacency, karena kemudian , dan pencarian brute force akan membutuhkan waktu . $N=|V|^2$ $2^{O(|V|)}$

Tapi kita bisa mendapatkan ikatan yang sama bahkan jika grafik diwakili oleh daftar adjacency, melalui algoritma waktu berjalan . Untuk melihat caranya, mari kita dapatkan -waktu algoritma untuk masalah keputusan NP-complete di mana kita diberi grafik dan dan kami ingin tahu apakah ada klik ukuran . $2^{\tilde O(\sqrt{|V| + |E|})}$ $2^{\tilde O(\sqrt{|V| + |E|})}$ $G=(V,E)$ $k$ $\geq k$

Algoritma hanya menghapus semua simpul derajat dan insiden tepi pada mereka, lalu melakukannya lagi, dan seterusnya, sampai kita dibiarkan dengan subgraf yang diinduksi oleh simpul di atas subset dari simpul, masing-masing derajat , atau dengan grafik kosong. Dalam kasus terakhir, kita tahu bahwa tidak ada klik ukuran bisa ada. Dalam kasus sebelumnya, kami melakukan pencarian brute-force berjalan dalam waktu kira-kira . Perhatikan bahwa dan, sehingga , dan pencarian brute-force berjalan dalam waktu sebenarnya berjalan dalam waktu . $< k$ $V'$ $\geq k$ $\geq k$ $|V'|^k$ $|E| \geq k\cdot |V'| /2$ $k\leq |V'|$ $|E| \geq k^2/2$ $|V'|^k$ $2^{O(\sqrt{|E|} \cdot \log |V|)}$

Luca Trevisan
sumber

12

Memang, untuk alasan-alasan seperti ini Impagliazzo, Paturi dan Zane berpendapat bahwa ketika menanyakan tentang kompleksitas vs Anda perlu mengatur menjadi ukuran saksi (yang Anda perlu mendefinisikan sebagai bagian dari masalah). Dalam kasus -clique saksi berukuranuntuk kecil , sementara, seperti yang Anda katakan, Anda dapat mengasumsikan wlog setidaknya adatepi dan ukuran input jauh lebih besar dari ukuran saksi.

2^{Ω (n)}

$2^{\Omega(n)}$

2^{o (n)}

$2^{o(n)}$

n

$n$

k

$k$

\log (\binom{| V |}{k}) \sim k \log | V |

$\log \binom{|V|}{k} \sim k\log |V|$

k

$k$

k | V |

$k|V|$

Boaz Barak

22

Karena setiap grafik planar pada simpul memiliki treewidth , semua masalah yang dipecahkan dalam waktu untuk grafik treewidth paling banyak ~ (ada BANYAK masalah seperti itu) memiliki algoritma subexponential-time pada grafik planar dengan menghitung pendekatan faktor konstan ke treewidth dalam polinomial-time (misalnya dengan menghitung branchwidth dengan algoritma ratcatcher) dan kemudian menjalankan algoritma treewidth, sehingga menghasilkan runtime dari bentuk untuk grafik pada simpul. Contohnya adalah Planar Independent Set dan Planar Dominating Set, yang tentu saja NP-lengkap. $n$ $O(\sqrt{n})$ $O^*(2^{O(k)})$ $k$ $O^*(2^{O(\sqrt{n})})$ $n$

Bart Jansen
sumber

15

Ada hubungan yang erat antara solvabilitas waktu sub-eksponensial (SUBEPT) dan traktabilitas parameter tetap (FPT). Tautan di antara mereka disediakan dalam makalah berikut.

Sebuah isomorfisme antara teori kompleksitas subeksponensial dan parameter , Yijia Chen dan Martin Grohe, 2006.

Singkatnya, mereka memperkenalkan gagasan yang disebut pemetaan miniaturisasi , yang memetakan masalah parameter ke dalam masalah parameter lain . Dengan melihat masalah normal sebagai masalah yang diparameterisasi oleh ukuran input, kami memiliki koneksi berikut. (Lihat teorema 16 di kertas) $(P,\nu)$ $(Q,\kappa)$

Teorema . dalam SUBEPT iff dalam FPT. $(P,\nu)$ $(Q,\kappa)$

Hati-hati dengan definisi di sini. Biasanya kita melihat masalah -clique sebagai parameter dalam , jadi tidak ada algoritma waktu sub-eksponensial untuk itu dengan asumsi hipotesis waktu Eksponensial. Tapi di sini kita membiarkan masalah diparameterisasi dengan ukuran input , sehingga masalahnya dapat diselesaikan dalam , yang merupakan algoritma waktu sub-eksponensial . Dan teorema mengatakan kepada kita bahwa masalah -clique adalah parameter tetap yang dapat ditelusur di bawah beberapa twist dari parameter , yang masuk akal. $k$ $k$ $O(m+n)$ $2^{O(\sqrt{m}\log m)}$ $k$ $k$

Secara umum, masalah dalam SUBEPT di bawah pengurangan SERF (keluarga pengurangan sub-eksponensial) dapat diubah menjadi masalah dalam FPT di bawah pengurangan FPT. (Teorema 20 dalam makalah) Lebih lanjut, koneksi bahkan lebih kuat karena mereka memberikan teorema isomorfisme antara seluruh hierarki masalah dalam teori kompleksitas waktu eksponensial dan teori kompleksitas parameter. (Teorema 25 dan 47) Meskipun isomorfisma tidak lengkap (ada beberapa tautan yang hilang di antara mereka), masih bagus untuk memiliki gambaran yang jelas tentang masalah ini, dan kita dapat mempelajari algoritma waktu sub-eksponensial melalui kompleksitas parameter.

Lihat survei oleh Jörg Flum dan Martin Grohe, bersama dengan Jacobo Torán, editor kolom kompleksitas, untuk informasi lebih lanjut.

Hsien-Chih Chang 張顯之
sumber

Iya nih. btw, Flum dan Grohe menulis survei; Toran adalah editor Kolom Kompleksitas.

Andy Drucker

@Andy: Terima kasih atas koreksinya. Saya akan memodifikasi artikelnya.

Hsien-Chih Chang 張顯之

12

contoh lain bisa berupa permainan Cop and Robber, yang merupakan NP-hard tetapi dapat dipecahkan dalam waktu pada grafik dengan n simpul. Catatan bibliografi BibTeX dalam XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Mengejar perampok cepat pada grafik. Teor Komputasi. Sci. 411 (7-9): 1167-1181 (2010) $2^{o(n)}$

XXYYXX
sumber

3

Ups, ini mungkin memalukan, tetapi saya sudah lama meyakini masalah sulit tidak memiliki algoritme waktu sub-eksponensial, hanya karena Hipotesis Waktu Eksponensial. :(

N P

$\mathsf{NP}$

Hsien-Chih Chang 張顯之

6

Tidak memalukan ... tapi, salah satu cara mudah untuk melihat ini tidak benar adalah dengan mengambil apa pun - Bahasa , dan kemudian membentuk 'empuk' versi di mana' ya ' contoh adalah dari bentuk , dengan , untuk beberapa tetap . Maka adalah , tetapi memiliki algoritma deterministik yang berjalan pada dasarnya .

N P

$NP$

L \in N P T I M E (n^{k})

$L \in NPTIME(n^k)$

L^{'}

$L'$

(x, 1^{| x |^{c}})

$(x, 1^{|x|^c})$

x \in L

$x \in L$

c > k

$c > k$

L^{'}

$L'$

N P

$NP$

2^{n^{k / c}}

$2^{n^{k/c}}$

Andy Drucker

7

Algoritme aproksimasi terbaik untuk klik memberikan faktor aproksimasi yang sangat buruk (ingat bahwa faktor aproksimasi adalah sepele). $n/\text{polylog } n$ $n$

Ada kekerasan hasil perkiraan di bawah berbagai asumsi kekerasan yang tidak cukup cocok dengan ini, tetapi masih memberikan kekerasan . Secara pribadi, saya percaya bahwa pendekatan untuk klik sama baiknya dengan algoritma waktu polinomial. $n^{1-o(1)}$ $n/\text{polylog } n$

Tetapi perkiraan untuk klik dapat dengan mudah dilakukan dalam waktu kuasi-polinomial. $n/\text{polylog } n$

Masalah NP-hard adalah masalah yang memiliki pengurangan waktu polinomial dari SAT. Bahkan jika SAT membutuhkan waktu , ini dapat diterjemahkan ke waktu untuk masalah yang kita kurangi menjadi. Jika yang terakhir memiliki ukuran input N, mungkin untuk konstanta kecil . $2^{\Omega(n)}$ $2^{\Omega(N^\epsilon)}$ $N=n^{1/\epsilon}$ $\epsilon$

Dana Moshkovitz
sumber

Masalah grafik yang sulit dipecahkan secara sub-responsif

Jawaban: