Perkiraan masalah genus

Apa yang saat ini diketahui tentang perkiraan masalah genus? Sebuah pencarian awal memberitahu saya bahwa faktor pendekatan konstan sepele untuk grafik cukup padat, dan $n^\epsilon$ -approximation algoritma telah dikesampingkan. Apakah informasi ini mutakhir, atau adakah batas yang lebih baik diketahui?

Semua hasil terbaik yang dipublikasikan muncul dalam makalah 1997 oleh Jianer Chen, Saroja P. Kanchi, dan Arkady Kanevsky.

• Untuk setiap tetap > $\varepsilon>0$ , menghitung genus grafik dengan kesalahan aditif $O(n^\varepsilon)$ adalah NP-hard.

• $n$$g$$\max\{4g, g+4n\}$

• Ada algoritma waktu-polinomial untuk grafik derajat-terbatas.$O(\sqrt{n})$

Ini adalah pertanyaan terbuka apakah ada algoritma pendekatan faktor konstan yang efisien.

Saya ingin menambahkan jawaban komprehensif Jɛ ff E bahwa sejauh pengetahuan saya, tidak ada batas bawah pada faktor perkiraan untuk masalah ini. Sejauh yang kita tahu, mungkin ada algoritma perkiraan yang selalu memberikan perkiraan faktor konstan (bahkan jika genusnya sangat kecil).

Makalah Chen, Kanchi, dan Kanevsky [CKK '97] hanya mengatakan bahwa menghitung genus dengan kesalahan aditif adalah NP-hard. Berikut ini adalah garis besar argumen mereka yang sangat informal. Akan jelas bahwa argumen ini tidak dapat digunakan untuk membuktikan batas bawah pada faktor aproksimasi. Pertimbangkan grafik sedemikian rupa sehingga sulit untuk menentukan apakah atau (untuk beberapa ) ; grafik seperti itu ada karena masalahnya NP-hard. Biarkan adalah jumlah simpul di . Biarkan menjadi konstanta besar. Ambil salinan yang terpisah dari grafik$O(n^{1-\varepsilon})$$G$$\mathrm{genus}(G) \leq g^*$$\mathrm{genus}(G) \geq g^*+1$$g^*$$n$$G$$k$$N = n^k$$G$dan pertimbangkan penyatuan mereka. Kemudian pada grafik diperoleh , NP-sulit untuk menentukan apakah atau . Artinya, NP-sulit untuk menghitung dengan kesalahan aditif , di mana . Konstruksi ini tidak memberi kita batas bawah pada faktor aproksimasi; rasio ke sama dengan rasio ke .$G'$$\mathrm{genus}(G') \leq N g^*$$\mathrm{genus}(G') \geq N(g^*+1)$$\mathrm{genus}(G')$$N = (Nn)^{k/{k+1}} = |V(G')|^{k/{k+1}} = |V(G')|^{1-\varepsilon}$$\varepsilon = 1/(k+1)$$N(g^*+1)$$Ng^*$$g^*+1$$g^*$