Menemukan set independen maksimal secara paralel

Pada grafik , kami melakukan proses berikut:$G(V,E)$

• Awalnya, semua node di berwarna.$V$
• Sementara ada node yang tidak berwarna dalam , setiap node yang tidak berwarna melakukan hal berikut: $V$
  • Memilih bilangan real acak dan mengirimkannya ke semua tetangganya;
  • Membandingkan jumlahnya dengan jumlah tetangganya; jika nomornya sendiri benar-benar terkecil, maka tetangganya dicat merah dan memberitahukan semua tetangganya.
  • Jika tetangga menjadi merah, maka simpul ini melukis dirinya sendiri hitam.

Sebagai contoh:

• Misalkan grafik adalah jalur: abcde.
• Misalkan angka pada langkah pertama adalah: 1-2-0-3-4.
• Node a dan c dicat merah; node b dan d dicat hitam.
• Pada langkah kedua, hanya simpul e yang tetap tidak berwarna; itu minimal sepele sehingga cat itu sendiri merah.

PERTANYAAN SAYA ADALAH: berapa jumlah rata-rata langkah yang dilakukan proses ini sebelum semua node diwarnai?

Perhitungan saya saat ini membawa saya ke perkiraan , yang tampaknya terlalu bagus untuk menjadi kenyataan. Berikut perhitungannya:$O(1)$

Pertimbangkan simpul dengan tetangga. Probabilitas bahwa akan menjadi yang terkecil di antara tetangganya adalah . Jika ini terjadi, maka dan semua tetangganya akan diwarnai. Jadi jumlah yang diharapkan dari simpul yang diwarnai setiap langkah adalah per node . Oleh karena itu jumlah total simpul yang diharapkan yang diwarnai setiap langkah adalah , jadi dalam waktu semua simpul akan diwarnai.$v$$d$$v$$1/(d+1)$$v$$(d+1)/(d+1)=1$ $O(n)$$O(1)$

Jika analisis ini salah (yang mungkin merupakan penyebabnya), lalu berapakah jumlah langkah aktual?

EDIT: Seperti dicatat oleh @JukkaSuomela, algoritma yang dijelaskan di atas adalah karena Metivier et al, 2011 dan dijelaskan dan dianalisis dalam catatan kuliah ini . Mereka membuktikan bahwa waktu menjalankan adalah .$O(\log n)$

Tapi, saya masih belum yakin bahwa analisis ini ketat. Dalam semua grafik yang saya periksa, tampaknya algoritma tersebut selesai dalam waktu yang diharapkan.$O(1)$

Pertanyaan saya sekarang: apakah grafik kasus terburuk di mana algoritma ini memang membutuhkan langkah-langkah ?$O(\log n)$

Ada kesalahan kecil, probabilitas menjadi minimal adalah . Itu tidak mengubah apa pun, tetapi masih layak untuk ditunjukkan.$v$$1/(d+1)$

Masalahnya adalah bahwa peristiwa yang Anda simpulkan tidak terpisah. Pertimbangkan dua simpul yang tidak berdekatan tetapi memiliki tetangga yang sama. Jika kedua simpul berakhir minimal di antara tetangganya, maka tetangganya akan dihitung berwarna dua kali.

Kita perlu memeriksa lebih dekat apa yang terjadi dalam suatu simpul. Mari kita hitung probabilitas (dan dengan demikian harapan variabel indikator) dari satu titik yang diwarnai.

Asumsikan demi analisis bahwa grafik adalah reguler dan tidak mengandung segitiga atau bujur sangkar. Kami akan menghitung kesempatan yang diberikan vertex tidak tidak mendapatkan berwarna. Ada kemungkinan: mungkin yang terkecil di antara tetangganya, mungkin menjadi yang terkecil kedua, ketiga terkecil, dan seterusnya ... Kami tidak tertarik pada kasus bahwa itu adalah yang terkecil, sejak itu ia mendapat berwarna.$d$$v$$d+1$$v$$v$

Jika adalah yang terkecil kedua, ada satu simpul yang lebih kecil. Probabilitas simpul ini menjadi terkecil di antara tetangganya adalah (dan dengan demikian semakin berwarna). Probabilitas tetangga yang tersisa terkecil di antara tetangga mereka adalah 0 (karena lebih kecil). Probabilitas total (dari tidak diwarnai) dari ini adalah .$v$$\frac{1}{d}$$v$$v$$v$ $\frac{1}{d+1}\cdot\frac{d-1}{d}$

Jika adalah yang terkecil ketiga, ada dua simpul yang lebih kecil. Probabilitas dari kasus ini adalah .$v$$\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$

Melanjutkan seperti ini, kami menemukan bahwa probabilitas bahwa tidak tidak mendapatkan berwarna adalah . Probabilitas dari titik tertentu yang diberi warna adalah . Saat , probabilitas menjadi .$v$$\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$$1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$$d\to \infty$$\frac{1}{e}\approx 0.368$

Oleh karena itu probabilitas bahwa simpul yang diberikan berwarna adalah konstan, sehingga jumlah simpul yang diharapkan berwarna pada langkah pertama memang .$O(n)$

Itu tidak membuat algoritma . Dengan asumsi probabilitas tetap konstan (yang tidak sepenuhnya dibenarkan mengingat node diwarnai dan tidak lagi berpartisipasi dalam algoritma, grafik tidak tetap reguler), pada langkah -th akan ada (dengan harapan) node tidak berwarna. Peluruhan bersifat eksponensial, sehingga algoritmanya mengambil langkah .$O(1)$$d$$k$${(\frac{1}{e})}^kn$$O(\log n)$

Mungkin orang lain akan dapat menawarkan analisis yang lebih tepat, tetapi dari argumentasi saya sepertinya algoritma tersebut adalah .$O(\log n)$