Beberapa masalah NP-hard yang eksponensial pada grafik umum adalah subeksponensial pada grafik planar karena treewidth paling banyak dan mereka eksponensial dalam treewidth.
Pada dasarnya saya tertarik jika ada algoritma subeksponensial untuk PLANAR SAT yang NP-complete.
Biarkan menjadi rumus CNF pada variabel dan klausa ke- adalah .
The grafik kejadian p. 5 dari adalah pada simpul dan tepi IFF atau .
ada di PLANAR SAT jika grafik insiden adalah planar.
Apakah ada algoritma subeksponensial untuk PLANAR SAT dalam hal ?
Saya tidak mengecualikan kemungkinan pengurangan SAT ke PLANAR SAT untuk membuat ini mungkin, meskipun SAT masih eksponensial dan subeksponensial karena peningkatan ukuran.
graph-theory
sat
reductions
joro
sumber
sumber
Jawaban:
Nah, Anda dapat menerapkan teorema pemisah planar bersamaan dengan pemrograman dinamis dan menjalankan waktu , di mananadalah jumlah simpul dalam grafik. Idenya adalah bahwa Anda mencoba semua tugas yang mungkin untuk simpul variabel pada pemisah, dan semua variabel yang disebutkan dalam klausa di pemisah (dengan asumsi masing-masing klausa memiliki jumlah variabel konstan).2O(n√) n
Jika simpul klausa besar, maka Anda harus menjadi sedikit lebih pintar - Anda harus menebak apakah akan menetapkannya ke subproblem sisi kiri atau kanan. Detail untuk hal-hal seperti itu cenderung berantakan dan tidak langsung, jadi saya tidak akan memberikan lebih banyak detail. Saya pikir makalah asli oleh Lipton dan Tarjan memecahkan masalah yang sama menggunakan ide yang sama, jika ingatan saya benar.
sumber