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

En el problema de la camarilla plantada, uno debe recuperar una $k$ camarilla plantada en un gráfico aleatorio Erdos-Renyi ( n , p $G(n,p)$ . Esto se ha visto principalmente para $p=\frac{1}{2}$ , en cuyo caso se sabe que puede resolverse en tiempo polinómico si$k > \sqrt{n}$ y conjeturado duro para$k< \sqrt{n}$ .

Mi pregunta es: ¿qué se sabe / cree sobre otros valores de $p$ ? Específicamente, cuando $p$ es una constante en $[0,1]$ ? ¿Existe evidencia de que, para cada valor de $p$ , existe algún $k=n^{\alpha}$ para el cual el problema es computacionalmente difícil?

Las referencias serían particularmente útiles, ya que no he logrado encontrar ninguna literatura que analice el problema para valores distintos de $p=\frac{1}{2}$ .

Si es constante, entonces el tamaño de la camarilla máxima en el modelo G ( n , p ) es casi siempre un múltiplo constante de log n , con la constante proporcional a log ( 1 / p ) . (Ver Bollobás, p.283 y Corolario 11.2.) Por lo tanto, cambiar p no debería afectar la dureza de plantar una camarilla con vértices ω ( log n ) siempre que la camarilla sea demasiado pequeña para que funcione un enfoque algorítmico existente. Por lo tanto, espero que con constante p ≠ 1 $p$$G(n,p)$$\log n$$\log (1/p)$$p$$\omega(\log n)$ la dureza de Clique plantado debe comportarse igual que el p = 1 / 2 caso, aunque es posible que el caso de p muy cerca de 0 o 1 podría comportarse de manera diferente.$p \ne 1/2$$p=1/2$$p$

En particular, para el mismo umbral de Ω ( n α ) para α = 1 / 2 para el tamaño de la camarilla plantado aplica, por encima del cual el problema se convierte en tiempo polinómico. El valor de α aquí es 1 / 2 (y no algún otro valor) porque la función Lovász theta de G ( n , p ) es casi seguramente entre 0,5 $p\ne 1/2$$\Omega(n^{\alpha})$$\alpha = 1/2$$\alpha$$1/2$$G(n,p)$ y2$0.5\sqrt{(1-p)/p}\sqrt{n}$ , por un resultado de Juhász. El algoritmo de Feige y Krauthgamer utiliza la función theta de Lovász para encontrar y certificar una camarilla más grande, por lo que se basa en este tamaño de umbral para la camarilla plantada.$2\sqrt{(1-p)/p}\sqrt{n}$

Por supuesto, puede haber un algoritmo diferente que no utiliza la función theta Lovász, y que para valores de lejos de 1 / 2 puede encontrar una camarilla plantado con, por ejemplo n 1 / 3 vértices. Por lo que puedo decir, esto todavía está abierto.$p$$1/2$$n^{1/3}$

Feige y Krauthgamer también discuten cuando no es constante pero depende de n , y está cerca de 0 o cerca de 1. En estos casos existen otros enfoques para encontrar camarillas plantadas, y el tamaño del umbral es diferente.$p$$n$

• Béla Bollobás, Gráficos aleatorios (2a edición), Cambridge University Press, 2001.
• Ferenc Juhász, el comportamiento asintótico de Lovász' función para grafos aleatorios$\vartheta$ , Combinatorica 2 (2) 153-155, 1982. doi: 10.1007 / BF02579314
• Uriel Feige y Robert Krauthgamer, Encontrar y certificar una gran camarilla oculta en un gráfico semialeatorio , 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

camarilla plantada para es un caso especial de este problema y nuevos resultados (límites inferiores) como se indica en p2, etc. e incluye referencias relacionadas. (2015)$p \neq \frac{1}{2}$

Mostramos que, suponiendo la hipótesis del tiempo exponencial (determinista), distinguiendo entre un gráfico con una inducida y un gráfico en el que todos los k- subgramas tienen densidad como máximo 1 - ε , requiere n ˜ Ω ( log n ) tiempo.$k$$k$$1 −\varepsilon$$n^{\tilde{\Omega}(\log n)}$

• ETH Dureza para Densest- -Subgraph con Perfectnessness$k$ / Braverman, Ko, Rubinstein, Weinstein

Aquí hay un nuevo artículo que tiene un algoritmo para p ≠ ½ arbitrario basado en un algoritmo SVD. ver p.4 para el análisis de la camarilla oculta (plantada).

UN ALGORITMO SVD SIMPLE PARA ENCONTRAR PARTICIONES OCULTAS Van Vu

Resumen. Encontrar una partición oculta en un entorno aleatorio es un problema general e importante, que contiene como subproblemas muchas preguntas famosas, como encontrar una camarilla oculta, encontrar un color oculto, encontrar una bipartición oculta, etc. En este documento, proporcionamos un SVD simple algoritmo para este propósito, respondiendo una pregunta de McSherry. Este algoritmo es muy fácil de implementar y funciona para gráficos dispersos con una densidad óptima.