Clique plantado em G (n, p), variando p

No problema da camarilha plantada, é necessário recuperar uma $k$ planta plantada no gráfico aleatório Erdos-Renyi $G(n,p)$ . Isso foi analisado principalmente para $p=\frac{1}{2}$ , caso em que se sabe que pode ser resolvido em tempo polinomial se$k > \sqrt{n}$ e conjecturado com força para$k< \sqrt{n}$ .

Minha pergunta é: o que se sabe / se acredita sobre outros valores de $p$ ? Especificamente, quando $p$ é uma constante em $[0,1]$ ? Existe evidência de que, para cada valor de $p$ , exista algum $k=n^{\alpha}$ para o qual o problema é computacionalmente difícil?

As referências seriam particularmente úteis, pois não consegui encontrar nenhuma literatura que analise o problema para outros valores além de $p=\frac{1}{2}$ .

Se for constante, o tamanho da camarilha máxima no modelo G ( n , p ) será quase sempre um múltiplo constante de log n , com a constante proporcional ao log ( 1 / p ) . (Veja Bollobás, p.283 e Corolário 11.2.) Portanto, a alteração p não deve afetar a dureza de plantar uma camarilha com vértices ω ( log n ) , desde que a camarilha seja muito pequena para que uma abordagem algorítmica existente funcione. Portanto, espero que, com constante p ≠ 1 $p$$G(n,p)$$\log n$$\log (1/p)$$p$$\omega(\log n)$ a dureza de Click Plantado deve comportar-se como o p = 1 / 2 caso, embora seja possível que o caso de p muito perto de 0 ou 1 pode comportar-se de maneira diferente.$p \ne 1/2$$p=1/2$$p$

$p\ne 1/2$$\Omega(n^{\alpha})$$\alpha = 1/2$$\alpha$$1/2$$G(n,p)$$0.5\sqrt{(1-p)/p}\sqrt{n}$$2\sqrt{(1-p)/p}\sqrt{n}$

$p$$1/2$$n^{1/3}$

$p$$n$

• Béla Bollobás, Random Graphs (2ª edição), Cambridge University Press, 2001.
• $\vartheta$
• Uriel Feige e Robert Krauthgamer, Encontrando e certificando uma grande camarilha oculta em um gráfico semi- aleatório, Random Structures & Algorithms 16 (2) 195–208, 2000. doi: 10.1002 / (SICI) 1098-2418 (200003) 16: 2 <195 :: AID-RSA5> 3.0.CO; 2-A

$p \neq \frac{1}{2}$

$k$$k$$1 −\varepsilon$$n^{\tilde{\Omega}(\log n)}$

• $k$

Aqui está um novo artigo que possui um algoritmo para p ½ ½ arbitrário com base em um algoritmo SVD. ver p.4 para análise de clique (plantado) oculto.

UM ALGORITMO SIMPLES DE SVD PARA ENCONTRAR PARTIÇÕES OCULTAS Van Vu

Resumo. Encontrar uma partição oculta em um ambiente aleatório é um problema geral e importante, que contém como subproblemas muitas perguntas famosas, como encontrar uma camarilha oculta, encontrar uma coloração oculta, encontrar uma bipartição oculta etc. Neste artigo, fornecemos um SVD simples algoritmo para esse fim, respondendo a uma pergunta de McSherry. Esse algoritmo é muito fácil de implementar e funciona para gráficos esparsos com densidade ideal.