Algoritme pendekatan untuk Set Independen Maksimum pada kelas grafik khusus

23

Kita tahu bahwa Maximum Independent Set (MIS) sulit diperkirakan dalam faktor untuk setiap kecuali P = NP. Apa sajakah kelas grafik khusus yang dapat diketahui algoritma perkiraannya dengan lebih baik? ϵ > 0n1−ϵϵ>0

Grafik apa yang diketahui algoritma waktu polinomial? Saya tahu untuk grafik sempurna ini diketahui, tetapi apakah ada kelas grafik menarik lainnya?

ds.algorithms graph-theory graph-algorithms approximation-algorithms Arindam Pal
sumber
1
Versi persisnya (non-aproksimasi) dari pertanyaan ini: cstheory.stackexchange.com/q/2503/109
András Salamon

Jawaban:

19

Ada daftar yang benar-benar luar biasa dari semua kelas grafik yang dikenal yang memiliki beberapa algoritma nontrivial untuk MIS: lihat entri ini di situs web kelas grafik.

Suresh Venkat
sumber
8
Daftar itu bertujuan khusus untuk algoritma yang tepat. Pada perkiraan, kelas utama mungkin PTAS pada grafik planar, grafik genus terikat, dan grafik H-minor-bebas.
Yixin Cao
Terima kasih Suresh. Daftarnya cukup komprehensif. Terima kasih juga kepada Yan untuk hasil perkiraannya.
Arindam Pal
2
referensi yang sesuai adalah: Brenda S. Baker: Algoritma Perkiraan untuk Masalah NP-Lengkap pada Grafik Planar. J. ACM 41 (1): 153-180 (1994); David Eppstein: Diameter dan Treewidth dalam Keluarga Grafik Tertutup Kecil. Algorithmica 27 (3): 275-291 (2000); Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algoritma Grafik Teori Kecil: Dekomposisi, Perkiraan, dan Pewarnaan. FOCS 2005: 637-646. Lihat juga: courses.csail.mit.edu/6.889/fall11/lectures/L08.html dan courses.csail.mit.edu/6.889/fall11/lectures/L09.html
Christian Sommer
12

Saya tidak memiliki gambaran yang baik tentang masalah ini, tetapi saya dapat memberikan beberapa contoh. Algoritma perkiraan sederhana adalah untuk menemukan beberapa urutan node dan dengan rakus memilih node untuk berada di set independen jika non-tetangga sebelumnya telah dipilih dalam set independen.

Jika grafik memiliki degenerasi maka menggunakan pemesanan degenerasi akan memberikan d- aproksimasi. maka untuk grafik degenerasi n 1 - ϵ kami memiliki perkiraan yang cukup baik.ddn1−ϵ

Ada beberapa teknik lain untuk perkiraan yang bekerja juga, tapi saya tidak mengenalnya dengan baik. Lihat: http://en.wikipedia.org/wiki/Baker%27s_technique dan http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

Untuk algoritma polinomial, memecahkan masalah dengan tepat. Tautan yang diberikan Suresh adalah yang terbaik. Graphclasses mana yang lebih menarik sulit untuk dikatakan.

kO(2kn)kO(log⁡n)

Martin Vatshelle
sumber
Seperti yang dikatakan Mohammad Al-Turkistany dalam jawabannya, grafik planar kubik adalah salah satu dari grafik yang tidak sempurna di mana set independen dapat diperkirakan. Semua grafik planar memiliki degenerasi paling banyak 5, dan grafik genus k memiliki degenerasi O (k) dan himpunan independen karenanya dapat diperkirakan.
Martin Vatshelle
5

Untuk kelas grafik planar kubik, makalah ini, Sebuah algoritma aproksimasi untuk masalah set independen maksimum dalam grafik planar kubik oleh Elarbi Choukhmane dan John Franco, memberikan algoritma perkiraan waktu polinomial. Faktor perkiraan algoritma mereka adalah 6/7.

Mohammad Al-Turkistany
sumber
1
Itu sudah usang oleh teknik Baker (FOCS'83) pada saat itu diterbitkan pada tahun 1986
David Eppstein
4

Saya belum memeriksa jawaban di atas, jadi saya minta maaf jika ada tumpang tindih. Berikut adalah kasus khusus di mana Anda dapat menyelesaikannya tepat dalam waktu polinomial. Jika grafik Anda G adalah grafik garis , maka jalankan algoritma waktu polinomial untuk menemukan grafik akar H, dan kemudian temukan pencocokan maksimum dalam H.

Babis Tsourakakis
sumber
Kedua grafik garis dan komplemen dari grafik garis bersifat polinomial dan dicakup oleh daftar yang diberikan oleh Suresh Venkat.
Martin Vatshelle
3

Dalam grafik perpotongan geometris, ada beberapa perkiraan menarik, PTAS, dan algoritma tepat sub-eksponensial. Lihat artikel Wikipedia Set Pengabaian Maksimum untuk survei.

Erel Segal-Halevi
sumber