Klik Tanam dalam G (n, p), bervariasi p

Dalam masalah klik yang ditanam, seseorang harus memulihkan -clique yang ditanam dalam grafik acak Erdos-Renyi . Ini sebagian besar telah dicari untuk , dalam hal ini dikenal sebagai polinomial-waktu yang dapat dipecahkan jika dan diduga sulit untuk .G ( n , p ) p = $k$$G(n,p)$ k>$p=\frac{1}{2}$ k<$k > \sqrt{n}$$k< \sqrt{n}$

Pertanyaan saya adalah: apa yang diketahui / dipercayai tentang nilai-nilai ? Secara khusus, kapan adalah konstanta dalam ? Apakah ada bukti bahwa, untuk setiap nilai , ada beberapa yang masalahnya sulit secara komputasi?p [ 0 , 1 ] p k = n $p$$p$$[0,1]$$p$$k=n^{\alpha}$

Referensi akan sangat membantu, karena saya belum berhasil menemukan literatur yang melihat masalah untuk nilai selain .$p=\frac{1}{2}$

Jika konstan, maka ukuran klik maksimum dalam model hampir di mana-mana merupakan kelipatan konstan dari , dengan konstanta sebanding dengan . (Lihat Bollobás, p.283 dan Corollary 11.2.) Oleh karena itu, mengubah seharusnya tidak mempengaruhi kekerasan penanaman klik dengan simpul selama klik tersebut terlalu kecil untuk pendekatan algoritmik yang ada untuk bekerja. Oleh karena itu saya berharap bahwa dengan konstan , kekerasan dari Perkebunan Klik harus berperilaku seperti halnya kasus, meskipun ada kemungkinan bahwa kasus sangat dekat dengan 0 atau 1 mungkin berperilaku berbeda.G ( n , p ) log n log ( 1 / p ) p ω ( log n ) p ≠ 1 / 2 p = 1 / 2 $p$$G(n,p)$$\log n$$\log (1/p)$$p$$\omega(\log n)$$p \ne 1/2$$p=1/2$$p$

Khususnya, untuk ambang yang sama dari untuk untuk ukuran klik yang ditanam berlaku, di atasnya masalah menjadi waktu polinomial. Nilai sini adalah (dan bukan nilai lain) karena fungsi theta Lovász dari hampir pasti antara dan , oleh hasil Juhász. Algoritma Feige dan Krauthgamer menggunakan fungsi Lovász theta untuk menemukan dan mengesahkan klik terbesar, sehingga bergantung pada ukuran ambang ini untuk klik yang ditanam.Ω ( n α ) α = 1 / 2 α 1 / 2 G ( n , p ) 0,5 $p\ne 1/2$$\Omega(n^{\alpha})$$\alpha = 1/2$$\alpha$$1/2$$G(n,p)$ 2$0.5\sqrt{(1-p)/p}\sqrt{n}$$2\sqrt{(1-p)/p}\sqrt{n}$

Tentu saja, mungkin ada algoritma yang berbeda yang tidak menggunakan fungsi theta Lovász, dan bahwa untuk nilai jauh dari dapat menemukan klik yang ditanam dengan simpul . Sejauh yang saya tahu ini masih terbuka.1 / 2 n 1 /$p$$1/2$$n^{1/3}$

Feige dan Krauthgamer juga membahas kapan tidak konstan tetapi tergantung pada , dan mendekati 0 atau mendekati 1. Dalam kasus ini, ada pendekatan lain untuk menemukan klik yang ditanam, dan ukuran ambangnya berbeda.$p$$n$

• Béla Bollobás, Grafik Acak (edisi ke-2), Cambridge University Press, 2001.
• Ferenc Juhász, Perilaku asimptotik fungsi Lovász ' untuk grafik acak$\vartheta$ , Combinatorica 2 (2) 153–155, 1982. doi: 10.1007 / BF02579314
• Uriel Feige dan Robert Krauthgamer, Menemukan dan mensertifikasi klik tersembunyi yang besar dalam grafik semi -acak, Struktur & Algoritma 16 (2) 195-208, 2000 acak. Doi: 10.1002 / (SICI) 1098-2418 (200003) 16: 2 <195 :: AID-RSA5> 3.0.CO; 2-A

klik yang ditanam untuk adalah kasus khusus dari masalah ini dan hasil baru (batas bawah) seperti yang dinyatakan pada p2 dll & itu termasuk referensi terkait. (2015)$p \neq \frac{1}{2}$

Kami menunjukkan bahwa, dengan asumsi (deterministik) Hipotesis Waktu Eksponensial, membedakan antara grafik dengan kli yang diinduksi dan grafik di mana semua subgraf memiliki kepadatan paling banyak , memerlukan waktu.k 1 - ε n ˜ Ω ( log n $k$$k$$1 −\varepsilon$$n^{\tilde{\Omega}(\log n)}$

• ETH Hardness for Densest- Subgraph dengan Kelengkapan Sempurna$k$ / Braverman, Ko, Rubinstein, Weinstein

Inilah kertas baru yang memiliki algoritma untuk p ≠ ½ berdasarkan algoritma SVD. lihat hal.4 untuk analisis klik tersembunyi (ditanam).

ALGORITMA SVD SEDERHANA UNTUK MENEMUKAN PARTISI TERSEMBUNYI Van Vu

Abstrak. Menemukan partisi tersembunyi di lingkungan acak adalah masalah umum dan penting, yang berisi banyak pertanyaan terkenal, seperti menemukan klik tersembunyi, menemukan pewarnaan tersembunyi, menemukan bipartisi tersembunyi dll. Dalam makalah ini, kami menyediakan SVD sederhana algoritma untuk tujuan ini, menjawab pertanyaan McSherry. Algoritma ini sangat mudah diimplementasikan dan berfungsi untuk grafik jarang dengan kepadatan optimal.