Menghitung konstanta Cheeger dari sebuah grafik , juga dikenal sebagai konstanta isoperimetri (karena pada dasarnya rasio area / volume minimum), dikenal sebagai NP-complete. Umumnya diperkirakan. Saya tertarik untuk mengetahui apakah algoritma polinom persis dikenal untuk kelas grafik khusus. Misalnya, apakah masih lengkap untuk grafik biasa ? Untuk grafik jarak-reguler ? (Saya belum mempelajari bukti kelengkapan NP yang ada untuk memeriksa asumsi mereka.) Petunjuk literatur dihargai — terima kasih!
ds.algorithms
reference-request
graph-algorithms
Joseph O'Rourke
sumber
sumber
Jawaban:
Perhatikan bahwa perkiraan pemotongan terkecil ke dalam memberikan perkiraan 2 α untuk konstanta Cheeger seperti yang didefinisikan. Berikut adalah beberapa makalah yang memberikan algoritma aproksimasi konstan untuk pemotongan sparsest dalam grafik terbatas:α 2α
Genus terikat: http://dl.acm.org/citation.cfm?id=1873619
Treewidth terikat: http://arxiv.org/abs/1006.3970
Lebih lanjut, http://arxiv.org/abs/1006.3970v2 membuktikan bahwa pemotongan sparsest adalah NP-hard untuk grafik dengan pathwidth 2, dan memiliki beberapa referensi lebih banyak untuk memperkirakan pemotongan sparsest pada instance terbatas.
Saya akan berasumsi bahwa untuk semua kelas grafik yang disebutkan dalam makalah, tidak ada algoritma yang diketahui (karena mereka tertarik pada perkiraan). Khususnya, jika sparsest cut adalah NP-hard untuk grafik dengan pathwidth 2, itu juga NP-hard untuk grafik treewidth 2, dan cutwidth 2. Saya kira itu tidak memberikan cukup banyak ruang .. mungkin ada lagi yang lebih baik parameterisasi untuk pemotongan sparsest.
Saya cukup yakin bahwa sparsest cut NP-hard pada grafik reguler tetapi tidak dapat menemukan referensi.
Per memperhatikan bahwa saya tidak berhati-hati ketika saya melihat kertas-kertas di atas. Hasil kekerasan adalah untuk potongan jarang berseragam. Komputasi potongan sparsest yang seragam atau konstanta Cheeger mudah pada pohon (WLOG potongan optimal memisahkan subtree). Dengan sedikit lebih banyak pekerjaan yang memberikan algoritma pemrograman dinamis untuk menghitung konstanta Cheeger pada grafik treewidth terbatas.
Tabel 1 dalam makalah 2 di atas juga menyebutkan hasil yang memberikan perkiraan konstan untuk grafik dengan minor yang dikecualikan.
sumber
Untuk solusi yang tepat dalam grafik planar, lihat Park and Phillips, STOC 93 . Ini pada dasarnya untuk seragam-tuntutan pemotongan paling rendah, dengan perbedaan kecil bahwa penyebutnya adalah | S | bukannya | S | * | VS |. Seperti yang ditunjukkan oleh Per, kasus tuntutan yang tidak seragam berbeda.
sumber