Grafik planar 3-warna di ?

Saya bertanya-tanya apakah tugas mencari planar 3-warna diketahui sebagai kompleksitas atau lebih rendah? Ini terasa seperti itu akan menjadi konsekuensi intuitif berdasarkan hasil pemisah planar, namun di wikipedia , itu hanya menyebutkan set independen, pohon Steiner, siklus Hamilton, dan TSP. Di bawah ini saya sertakan beberapa alasan yang menurut saya hampir mencapai batasan ini.$O\left(c^{\sqrt{n}}\right)$

Dengan diagram keputusan tereduksi nol (ZDD), saya yakin Anda bisa mendapatkan , dan saya ingin tahu bagaimana saya bisa melakukan yang lebih baik. Apa yang saya pikirkan agak sederhana. Catatan: selama ini, ZDD yang saya jelaskan adalah ternary, tapi saya pikir itu tidak terlalu penting. Untuk ZDD, diberi urutan, , dari simpul ke warna, jumlah node pada langkah akan eksponensial sehubungan dengan ukuran perbatasan, .$O\left(c^{O(log_2(n)\sqrt{n})}\right)$$L = \{v_1 \dots v_n\}$$i$$F_i = \{v_k | k < i \land v_k~v_j, j \geq i \}$

Untuk membuat pemesanan Anda , Anda dapat membuat pohon dekomposisi cabang yang optimal, , dalam waktu polinomial, yang memiliki lebar paling banyak . Kemudian, pilih daun acak dari untuk menjadi root. Dengan BFS, timbang setiap tepi dengan jumlah daun yang tidak terhubung ke jika Anda harus menghapus dari . Kemudian, lakukan DFS untuk akhirnya membuat , selalu turun paling jauh dari , memilih satu dengan bobot paling sedikit jika ada dasi, dan memilih sewenang-wenang jika masih ada dasi. Ketika kita mencapai daun, tambahkan$L$$b$$\sqrt{n}$$v’$$b$$e$$v’$$e$$b$$L$$v’$$(u,v)$$u$/ untuk jika salah tidak di . Biarkan menjadi komponen diinduksi dalam oleh simpul mengunjungi ketika kita menambahkan ke . Kemudian, dibatasi oleh lebar cabang kali jumlah tepi perlu dihapus dari untuk mendapatkan komponen . dibatasi kira-kira oleh dari simpul dalam , yang linear ke karena kita sedang berhadapan dengan grafik planar.$v$$L$$L$$c_i$$b$$v_i$$L$$F_i$$x_i$$b$$c_i$$x$$log_2$$b$$n$

Dengan itu, Anda memeriksa ketiga warna untuk setiap node untuk masing-masing perbatasan dan selesai.$n$

Saya merekomendasikan membaca Bagian 7 dan 14 dalam buku yang sangat bagus oleh Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, dan Saurabh .

Singkatnya, Gu dan Tamaki memberikan algoritma waktu kuadratik yang menemukan dekomposisi cabang dari grafik planar lebar paling banyak . Kemudian Robertson dan Seymour dalam (5.1) memberikan dekomposisi pohon dengan lebar kurang dari . Kemudian algoritma pemrograman dinamis klasik (lihat, misalnya, Marx ) memecahkan -Coloring in time .$3\sqrt{n}$ 9 √$\frac{9\sqrt{n}}{2}$ 33 9 √$3$$3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$

Di sisi lain, diketahui ( Lichtenstein ) bahwa di bawah Hipotesis Eksponensial Waktu (ETH), masalah Planar -SAT adalah -hard. Dan pengurangan dari Planar -SAT ke Planar -Coloring menyiratkan bahwa di bawah ETH tidak ada algoritma yang menyelesaikan Planar -Coloring dalam waktu .$3$$2^{\Omega(\sqrt{n})}$$3$$3$$3$$2^{o(\sqrt{n})}$