Menghitung jumlah penutup simpul: kapan sulit?

Pertimbangkan masalah # P-complete untuk menghitung jumlah penutup simpul dari grafik yang diberikan .$G = (V, E)$

Saya ingin tahu apakah ada hasil yang menunjukkan bagaimana kekerasan masalah tersebut bervariasi dengan beberapa parameter (misalnya, ).$G$$d = \frac{|E|}{|V|}$

Sensasi saya adalah bahwa masalahnya harus lebih mudah baik ketika jarang dan ketika padat, sementara itu harus sulit ketika "di tengah". Benarkah ini masalahnya?$G$$G$$G$

Masalah #VC menghitung jumlah simpul penutup dari grafik yang diberikan tetap # P-hard untuk grafik 3-reguler; lihat misalnya [Greenhill, 2000].

Untuk menunjukkan bahwa masalah #VC tetap # P-hard untuk grafik dengan paling banyak edge, di mana adalah jumlah simpul dan , kurangi dari kasus 3-reguler dengan menambahkan besar set cukup independen (ukuran linier). Jumlah penutup simpul tetap sama jika Anda menambahkan satu set independen.$c\cdot n$$n$$0<c<3/2$

Demikian pula, untuk menunjukkan bahwa masalah #VC tetap # P-keras untuk grafik dengan setidaknya tepi, di mana adalah jumlah simpul dan , kurangi dari #VC dengan menambahkan a komponen klik yang cukup besar (ukuran linier). Jumlah penutup simpul dikalikan dengan jika Anda menambahkan klik ukuran ke grafik.$c\cdot n^2$$n$$0<c<1/2$$p+1$$p$

Catherine S. Greenhill: Kompleksitas penghitungan warna dan set independen dalam grafik tipis dan hypergraphs . Kompleksitas Komputasi 9 (1): 52-72 (2000)

Mengikuti jawaban Yaroslav, Luby dan Vigoda adalah orang pertama yang menunjukkan FPRAS untuk #IS dalam kondisi kepadatan (tingkat maksimum 4, yang saya kira lebih lemah dari hasil Weitz), sementara Dyer, Frieze dan Jerrum menunjukkan bahwa tidak ada FPRAS untuk #IS jika derajat maksimum grafik adalah 25 kecuali RP = NP.

Referensi:

Martin Dyer, Alan Frieze, dan Mark Jerrum. Pada menghitung set independen dalam grafik jarang. FOCS 1999.

Michael Luby dan Eric Vigoda. Kira-kira menghitung hingga empat. STOC 1997.

Lihat juga catatan kuliah ETH Jerrum, "Menghitung, mengambil sampel, dan mengintegrasikan: algoritma dan kompleksitas".

Sehubungan dengan kompleksitas waktu eksponensial, instance umum dan instance dengan derajat maksimum konstan sama-sama keras: Lemma sparsifikasi Impagliazzo, Paturi, Zane (2002) menunjukkan bahwa -beberapa contoh d -Sat dapat direduksi menjadi contoh d -Sat dengan paling banyak f ( d , ϵ ) ⋅ n klausa dalam exp waktu ( ϵ n ) . Seperti yang diamati dalam kerja bersama dengan Husfeldt dan Wahlén, lemma sparsifikasi bekerja untuk versi penghitungan d -Sat juga, dan terutama untuk kasus penghitungan $n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (yang setara dengan menghitung set independen dan menghitung simpul penutup).

Selain itu, menghitung set independen dalam grafik -vertex tidak dapat dilakukan dalam exp waktu ( o ( n ) ) kecuali hipotesis waktu eksponensial gagal. Ini adalah pengamatan yang belum dipublikasikan yang diumumkan dalam ceramah selama Penghitungan Komputasi Seminar Dagstuhl .$n$$\exp(o(n))$

Set adalah vertex cover jika komplemennya adalah set independen, oleh karena itu masalah ini setara dengan menghitung set independen.

Penghitungan aljabar set independen adalah FPT untuk grafik lebar klik terikat terbatas. Misalnya, lihat Courcelle's "Sebuah polinom interlace multivariat dan komputasinya untuk grafik lebar klik terikat", di mana mereka menghitung generalisasi polinomial kemerdekaan. Menambahkan koefisien polinomial kemerdekaan memberikan jumlah set independen.

Grafik dengan derajat 3 maksimum dapat memiliki lebar klik tidak terikat.

$d$$\lambda$

_{(sumber: yaroslavvb.com )}

$\lambda=1$

$d$$\lambda$$d$