menghitung set independen

8

Algoritme / teknik matematika apa yang tersedia untuk persis / kira-kira menghitung jumlah set independen?

Apakah / Apakah ada referensi yang baik / referensi yang baik tentang topik ini?

Saya tertarik pada grafik reguler.

ds.algorithms reference-request graph-theory approximation-algorithms counting-complexity vs.
sumber

1

Googling "menghitung set reguler grafik reguler" menghasilkan makalah ini sebagai hasil ketiga, yang memberikan batas atas.

Anthony Labarre

7

Masalahnya dapat disajikan kembali sebagai # 2SAT. Lihat

http://en.wikipedia.org/wiki/2-satisfiability

di bawah bagian "Menghitung jumlah tugas memuaskan" untuk beberapa referensi ke algoritma penghitungan tepat terbaik saat ini.

Andreas Björklund
sumber

Saya tidak melihat koneksi langsung ke set independen di bagian itu meskipun di bagian selanjutnya mereka memiliki referensi ke grafik bisplit (grafik yang dapat dipisah-pisahkan ke dalam set independen dan grafik lengkap). Saya tidak berpikir saya mencari ini !! Apakah saya kehilangan koneksi?

vs

5

@vs bagaimana dengan: untuk

, untuk setiap

, memiliki variabel

, dan untuk setiap

memiliki klausa

. semua variabel yang disetel ke true berhubungan dengan set independen.

G = (V, E)

$G = (V, E)$

u \in V

$u \in V$

x_{u}

$x_u$

(u, v) \in E

$(u, v) \in E$

\neg x_{u} \lor \neg x_{v}

$\neg x_u \vee \neg x_v$

Sasho Nikolov

Apakah ada teknik pewarnaan yang serupa?

vs

@vs Ya, konstruksi yang sama dengan ukuran domain yang lebih besar.

Tyson Williams

5

Untuk perkiraan penghitungan, makalah berikut (juga dalam APPROX-RANDOM 2011)

http://arxiv.org/abs/1105.5131

menggambarkan keadaan seni.

Seperti yang disebutkan Anthony Labarre dalam komentar di atas, ada terobosan terbaru dan tak terduga oleh Yufei Zhao yang menunjukkan batas atas yang ketat pada jumlah set independen dalam grafik -vertex regular. Buktinya menggunakan bijih yang sangat pintar. Contoh ekstrem, yang diduga oleh Alon dan Kahn dan berasal dari tahun 1991, hanyalah perpaduan yang tidak terpisahkan dari banyak salinan grafik bipartit lengkap reguler. $n$ $d$ $d$

Bidang penelitian ini mengacu pada banyak metode matematika dan algoritmik, dan merupakan bidang yang menarik tidak hanya bagi para ilmuwan komputer teoretis, tetapi juga untuk sejumlah teori, probabilis, kombinatorialis, fisikawan statistik, dan banyak lagi. Dua makalah baru-baru ini mungkin memberi Anda awal yang baik, meskipun ada banyak koleksi makalah yang mendalam dan menarik tentang topik ini selama beberapa dekade.

RJK
sumber

4

Untuk melengkapi jawaban dari @RJK, mulai kemarin, ada "keadaan terkini".

Sly and Sun show

$d \ge 3$ $\lambda > \lambda_c(d) = \frac{(d−1)^{d-1}}{(d-2)^d}$ $\lambda$ $d$

$\lambda < \lambda_c(d)$

$\lambda = \lambda_c(d)$

Tyson Williams
sumber

Tahukah Anda jika hasil ini berlaku untuk grafik dengan struktur spesifik seperti produk kuat, lemah (dll) yang grafik dasarnya adalah dergee kurang dari 3 dan yang memiliki nilai lambda lebih kecil dari yang di atas?

vs

@ v Grafik-grafik ini teratur?

Tyson Williams

Iya. Tetapi apakah hasilnya menyiratkan untuk semua grafik biasa, tanpa peringatan ?? (Saya berpikir sesuatu yang analog dengan ini - kita tahu itu adalah NP sulit untuk ML decode kode linier .. tetapi sangat sulit untuk menunjukkan kode non-sepele spesifik seperti kode RS dan juga diketahui ada kode di mana ML decoding mudah) Tentu saja kelihatannya hasil di sini berlaku untuk semua grafik reguler .. tetapi ada kasus di mana simetri grafik dapat membantu juga dan saya tidak melihat grafik ini (di kertas) diasumsikan memiliki simetri apa pun sama sekali!!

vs

1

d

$d$

menghitung set independen

Jawaban: