Contoh waktu polinomial yang dapat dipecahkan dari Max-Sat

18

Masalahnya Max-Sat meminta Anda untuk menemukan penugasan formula CNF yang memenuhi klausa sebanyak mungkin.

Untuk masalah SAT yang lebih sederhana, ada banyak kasus khusus yang diketahui yang dapat diselesaikan dalam waktu polinomial, misalnya kita dapat menyelesaikan 2-SAT dalam waktu polinomial.

Untuk Max-Sat situasinya berbeda karena Max-Sat adalah NP-hard bahkan untuk formula 2-CNF (setiap klausa hanya berisi 2 variabel).

Apakah ada input khusus yang menarik yang Max-Sat jumlahnya polinomial?

Khususnya saya akan tertarik pada referensi standar untuk memecahkan Max-Sat ketika grafik incedence telah membatasi treewidth.

sat treewidth max2sat Martin Vatshelle
sumber
3
Planar max-cut adalah case khusus max-cut, yang (dalam arti tertentu) adalah case khusus max-2-sat.
Jukka Suomela

Jawaban:

6

Ini tidak langsung menjawab masalah Max-SAT Anda, tetapi referensi mungkin memandu Anda ke jawaban lengkap.

Szeider menunjukkan bahwa Satisfiability adalah parameter-trable yang dapat ditelusuri ketika parameter oleh treewidth dari grafik kejadian. Samer dan Szeider memberikan algoritma pemrograman dinamis yang efisien.

Referensi

S. Szeider. Pada parameterisasi traktivasi SAT yang tetap pada parameter. Di Proc. Konferensi Internasional ke-6 tentang Teori dan Aplikasi Kepuasan (SAT'03), Kertas yang Dipilih dan Direvisi, vol. 2919 dari LNCS, halaman 188–202. Springer-Verlag, 2004.

M. Samer dan S. Szeider. Algoritma untuk penghitungan model proposisional. Di Proc. Konferensi Internasional ke-14 tentang Logika untuk Pemrograman, Kecerdasan dan Penalaran Artifisial (LPAR'07), vol. 4790 LNCS, halaman 484–498. Springer-Verlag, 2007.

Samer dan Szeider, traktabilitas parameter-tetap. Dalam A. Biere, M. Heule, H. van Maaren, dan T. Walsh, editor, Buku Pegangan Kemampuan, bagian 1, bab 13. IOS Press

Mohammad Al-Turkistany
sumber
Saya tahu beberapa karya Stefan Szeiders, sebuah makalah yang lebih baru menunjukkan bahwa #SAT adalah polinomial ketika grafik incedence telah membatasi klik-lebar yang juga menunjukkan batas-lebar pohon (meskipun di sini kita memiliki runtime XP bukan FPT). Friedrich Slivovsky dan Stefan Szeider, Penghitungan Model untuk Rumus-Batas Lebar, Algoritma dan Komputasi, vol. 8283, hlm. 677-687, LNCS, 2013 Saya tahu bahwa jenis hasil ini sering diterjemahkan ke dalam MAX-SAT, tetapi akan jauh lebih mudah memiliki referensi di mana ini sudah dilakukan daripada melakukannya sendiri.
Martin Vatshelle
0

Kami menemukan satu jenis properti seperti itu:

FFxCxCCCxx

lihat: http://arxiv.org/abs/1402.6485

Apakah ada properti lain yang diketahui?

Martin Vatshelle
sumber