Kompleksitas penghitungan semua subgraph yang terhubung

Biarkan G menjadi grafik yang terhubung.

Apa kompleksitas penghitungan semua subgraph yang terhubung jika G dari tipe berikut?

• G bersifat umum.
• G adalah planar.
• G adalah bipartit.

Saya tidak peduli dengan struktur atau ..., hanya perlu menghitung semua subgraph yang terhubung! Saya juga tertarik pada kompleksitas penghitungan semua subgraph yang terhubung dengan tepat k node dalam G.

Pointer ke kertas dan buku juga disambut!

Welsh menyatakan bahwa masalah # P-selesai bahkan dalam kasus yang paling terbatas (menghitung jumlah subgraph yang terhubung dari grafik bipartit planar). Lihat bagian bawah halaman 305 dalam Welsh, Dominic (1997), "Perkiraan Menghitung", Survei di Combinatorics , Bailey, RA, ed., Cambridge University Press, hlm. 287-324.

Namun dalam konteksnya, saya bertanya-tanya apakah dia benar-benar berarti terhubung dengan subgraph yang terhubung. Dan itu membuat saya bertanya-tanya versi mana dari masalah yang Anda inginkan: subgraph spanning terkoneksi, subgraph terkoneksi yang tidak perlu spanning, atau subgraph yang diinduksi terhubung?

Ini adalah jawaban atas jawaban David. Tanpa melihat buku itu, saya kira masalahnya adalah menghitung subgraf spanning terhubung, karena ini adalah titik x = 1 y = 2 dari polinomial Tutte, dan penulis tertarik pada hal itu. Tapi sebenarnya saya pikir tiga masalah mengurangi cukup mudah dari menghitung masalah subgraph spanning terhubung. Pengurangan berikut harus bekerja baik untuk penghitungan yang tepat atau perkiraan, meskipun saya pikir masalah untuk perkiraan masih terbuka.

$K_A$$A$

$K_A$$A$

$\#P$