Posadzona klika w G (n, p), zmieniająca się p

W przypadku problemu sadzonej kliki należy odzyskać $k$-klinka posadzona na losowym wykresie Erdosa-Renyi $G(n,p)$. To było głównie rozpatrywane$p=\frac{1}{2}$, w którym to przypadku wiadomo, że można rozwiązać czas wielomianowy, jeśli $k > \sqrt{n}$ i przypuszczalnie trudne $k< \sqrt{n}$.

Moje pytanie brzmi: co wiadomo / uważa się o innych wartościach $p$? W szczególności kiedy$p$ jest stałą w $[0,1]$? Czy istnieją dowody na to, że dla każdej takiej wartości$p$istnieje kilka $k=n^{\alpha}$ dla którego problem jest trudny obliczeniowo?

Odniesienia byłyby szczególnie pomocne, ponieważ nie udało mi się znaleźć żadnej literatury, która dotyczyłaby problemu dla wartości innych niż $p=\frac{1}{2}$.

Gdyby $p$ jest stała, to wielkość maksymalnej kliki w $G(n,p)$ model jest prawie wszędzie stałą wielokrotnością $\log n$, ze stałą proporcjonalną do $\log (1/p)$. (Patrz Bollobás, s. 283 i wniosek 11.2.) Zmiana$p$ nie powinien zatem wpływać na twardość sadzenia kliki $\omega(\log n)$wierzchołki, o ile klika jest zbyt mała, aby działało istniejące algorytmiczne podejście. Dlatego oczekuję tego ze stałą$p \ne 1/2$ twardość posadzonej kliki powinna zachowywać się tak jak $p=1/2$ przypadek, chociaż możliwe jest, że przypadek $p$ bardzo blisko 0 lub 1 może zachowywać się inaczej.

W szczególności dla $p\ne 1/2$ ten sam próg wynoszący $\Omega(n^{\alpha})$ dla $\alpha = 1/2$dotyczy wielkości sadzonej kliki, powyżej której problem staje się czasem wielomianowym. Wartość$\alpha$ tutaj jest $1/2$ (i żadnej innej wartości), ponieważ funkcja theta Lovásza $G(n,p)$ jest prawie na pewno pomiędzy $0.5\sqrt{(1-p)/p}\sqrt{n}$ i $2\sqrt{(1-p)/p}\sqrt{n}$, w wyniku Juhásza. Algorytm Feige i Krauthgamer używa funkcji theta Lovásza do znalezienia i certyfikacji największej kliki, więc opiera się na tej wartości progowej dla posadzonej kliki.

Oczywiście może istnieć inny algorytm, który nie korzysta z funkcji theta Lovásza i dla wartości $p$ daleko od $1/2$ mogę znaleźć posadzoną klikę z powiedzmy $n^{1/3}$wierzchołki. O ile wiem, to wciąż jest otwarte.

Feige i Krauthgamer również dyskutują, kiedy $p$ nie jest stały, ale zależy od $n$, i jest albo bliski 0, albo bliski 1. W tych przypadkach istnieją inne podejścia do znalezienia posadzonych klik, a wielkość progu jest inna.

• Béla Bollobás, Random Graphs (2. edycja), Cambridge University Press, 2001.
• Ferenc Juhász, asymptotyczne zachowanie Lovásza ”$\vartheta$funkcja losowych wykresów , Combinatorica 2 (2) 153–155, 1982. doi: 10.1007 / BF02579314
• Uriel Feige i Robert Krauthgamer, Znalezienie i certyfikacja dużej ukrytej kliki na grafie półirandomowym , Struktury losowe i algorytmy 16 (2) 195–208, 2000. doi: 10.1002 / (SICI) 1098-2418 (200003) 16: 2 <195 :: AID-RSA5> 3.0.CO; 2-A

posadzona klika dla $p \neq \frac{1}{2}$jest szczególnym przypadkiem tego problemu i nowych wyników (dolne granice), jak podano na p2 itp., i obejmuje powiązane odnośniki. (2015)

Pokazujemy, że przyjmując (deterministyczną) hipotezę czasu wykładniczego, rozróżniając wykres z indukowaną $k$-klika i wykres, na którym wszystko $k$-subgrrafy mają co najwyżej gęstość $1 −\varepsilon$, wymaga $n^{\tilde{\Omega}(\log n)}$ czas.

• Twardość ETH dla Densest-$k$-Subgraph z Perfect Completeness / Braverman, Ko, Rubinstein, Weinstein

oto nowy artykuł, który ma algorytm dla arbitralnego p ≠ ½ oparty na algorytmie SVD. analiza ukrytej (posadzonej) kliki na str. 4.

PROSTY Algorytm SVD DO ZNALEZIENIA UKRYTYCH PRZEGRÓD Van Vu

Abstrakcyjny. Znalezienie ukrytej partycji w losowym środowisku jest ogólnym i ważnym problemem, który zawiera jako podproblem wiele znanych pytań, takich jak znalezienie ukrytej kliki, znalezienie ukrytej kolorystyki, znalezienie ukrytej dwuczęściowej itp. W tym artykule przedstawiamy prosty SVD algorytm do tego celu, odpowiadający na pytanie McSherry. Ten algorytm jest bardzo łatwy do wdrożenia i działa w przypadku rzadkich wykresów o optymalnej gęstości.