Camarilla plantada

Subgrafo completo agregado a un gráfico aleatorio

Una camarilla plantada de 15 vértices (vértices azules y bordes superiores) en un gráfico aleatorio de 32 vértices (todos los vértices y bordes inferiores). Cada par de vértices azules es adyacente; los pares restantes son adyacentes aleatoriamente con probabilidad 1/2.

En teoría de la complejidad computacional , una camarilla plantada o una camarilla oculta en un gráfico no dirigido es una camarilla formada a partir de otro gráfico seleccionando un subconjunto de vértices y agregando aristas entre cada par de vértices en el subconjunto. El problema de la camarilla plantada es el problema algorítmico de distinguir gráficos aleatorios de gráficos que tienen una camarilla plantada. Ésta es una variación del problema de la camarilla ; puede resolverse en tiempo cuasipolinomial, pero se conjetura que no se puede resolver en tiempo polinómico para valores intermedios del tamaño de la camarilla. La conjetura de que no existe una solución temporal polinomial se llama conjetura de la camarilla plantada ; se ha utilizado como un supuesto de dureza computacional .

Definición

Una camarilla en un gráfico es un subconjunto de vértices, todos los cuales son adyacentes entre sí. Una camarilla plantada es una camarilla creada a partir de otro gráfico agregando aristas entre todos los pares de un subconjunto seleccionado de vértices.

El problema de la camarilla plantada se puede formalizar como un problema de decisión sobre una distribución aleatoria en gráficos, parametrizado por dos números, n (el número de vértices) y k (el tamaño de la camarilla). Estos parámetros se pueden utilizar para generar un gráfico mediante el siguiente proceso aleatorio: ^[1]

1. Cree un gráfico aleatorio Erdős-Rényi en n vértices eligiendo de forma independiente para cada par de vértices si se incluye un borde que conecte ese par, con una probabilidad de 1/2 para cada par.
2. Decide si agregar o no una camarilla al gráfico, con probabilidad 1/2; si no, devuelva el gráfico formado en el paso 1.
3. Elija aleatoriamente un subconjunto de k de los n vértices y agregue un borde (si aún no hay uno presente) entre cada par de los vértices seleccionados.

El problema es entonces determinar algorítmicamente si uno de los grafos resultantes de este proceso contiene una camarilla de al menos k vértices.

Límites superior e inferior

Existe una función tal que asintóticamente casi con seguridad, el tamaño de la camarilla más grande en un gráfico aleatorio de n -vértices es o , ^[2] y existe alguna constante tal que el número esperado de camarillas de tamaño converge al infinito. En consecuencia, se debe esperar que la plantación de un grupo de tamaño no pueda detectarse con alta probabilidad. ${\displaystyle f(n)\sim 2\log _{2}n}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)+1}$ ${\displaystyle c}$ ${\displaystyle \geq f(n)-c}$ ${\displaystyle \sim 2\log _{2}n}$

Según el teorema del límite central , los grados de los vértices del gráfico aleatorio se distribuirían cerca de una distribución normal estándar con media y desviación estándar . En consecuencia, cuando esté en el orden crearía un cambio detectable en la forma de la distribución. Es decir, si traza la distribución de grados del vértice, parecería una curva de campana deformada. Por tanto, el rango de valores más interesante para el parámetro k se encuentra entre estos dos valores, ^[1] ${\displaystyle {\frac {n}{2}}}$ ${\displaystyle {\frac {\sqrt {n}}{2}}}$ ${\displaystyle k}$ ${\displaystyle {\sqrt {n}}}$

${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}.}$

Algoritmos

Grandes camarillas

Para valores suficientemente grandes del parámetro k , el problema de la camarilla plantada se puede resolver (con alta probabilidad) en tiempo polinómico. ^[1]

Kučera (1995) observa que, entonces, casi seguramente todos los vértices de la camarilla plantada tienen un grado más alto que todos los vértices fuera de la camarilla, lo que hace que la camarilla sea muy fácil de encontrar. Describe una modificación del proceso aleatorio para generar instancias de camarilla plantada, que hace que los grados de los vértices sean más uniformes incluso para valores grandes de  k , pero muestra que a pesar de esta modificación la camarilla plantada aún se puede encontrar rápidamente. ^[3] ${\displaystyle k=\Omega ({\sqrt {n\log n}})}$

Alon, Krivelevich y Sudakov (1998) demuestran que una camarilla plantada se puede encontrar con alta probabilidad mediante el siguiente método: ${\displaystyle k>10{\sqrt {n}}}$

1. Calcule el vector propio de la matriz de adyacencia correspondiente a su segundo valor propio más alto .
2. Seleccione los k vértices cuyas coordenadas en este vector propio tengan los valores absolutos más grandes .
3. Devuelve el conjunto de vértices adyacentes a al menos 3/4 de los vértices seleccionados.

Muestran cómo modificar esta técnica para que continúe funcionando siempre que k sea al menos proporcional a algún múltiplo de la raíz cuadrada del número de vértices. ^[4] También se pueden encontrar grandes camarillas plantadas utilizando programación semidefinida . ^[5] Una técnica combinatoria basada en muestreo aleatorio de vértices puede lograr el mismo límite en k y se ejecuta en tiempo lineal . ^[6]

tiempo cuasipolinomial

También es posible resolver el problema de la camarilla plantada, independientemente de la elección de k , en un tiempo cuasipolinomial . ^[7] Debido a que la camarilla más grande en un gráfico aleatorio generalmente tiene un tamaño cercano a 2 log ₂ n , ^[8] una camarilla plantada de tamaño k (si existe) se puede encontrar con alta probabilidad mediante el siguiente método:

1. Recorre todos los conjuntos S de vértices. ${\displaystyle \min(k,3\log _{2}n)}$
2. Para cada elección de S , pruebe si S es una camarilla. Si es así, y , devuelve S . De lo contrario, encuentre el conjunto T de vértices que son adyacentes a todos los vértices en S. Si , devuelve T . ${\displaystyle |S|=k}$ ${\displaystyle |T|\geq k}$

El tiempo de ejecución de este algoritmo es cuasipolinomial, porque hay muchas opciones cuasipolinomiales de S para recorrer. Se garantiza que este método probará un conjunto S que sea un subconjunto de la camarilla plantada; con alta probabilidad, el conjunto T estará formado únicamente por otros miembros de la camarilla plantada.

Como supuesto de dureza

La conjetura de la camarilla plantada es la conjetura de que no existe un algoritmo de tiempo polinómico que tome como entrada los gráficos producidos por el proceso de la camarilla plantada y distinga los que tienen camarillas plantadas de los que no las tienen con una probabilidad significativamente mejor que el azar. ^[9]

Hazan y Krauthgamer (2011) utilizaron el supuesto de que encontrar camarillas plantadas es difícil como supuesto de dureza computacional para demostrar que, de ser así, también es difícil aproximarse al mejor equilibrio de Nash en un juego de dos jugadores. ^[7] La ​​conjetura de la camarilla plantada también se ha utilizado como un supuesto de dureza para mostrar la dificultad de probar la propiedad k -independencia de distribuciones aleatorias, ^[10] encontrar clústeres en redes sociales, ^[11] y el aprendizaje automático . ^[12]

Referencias

1. , Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno, Cambridge University Press, págs. 362–363, ISBN 9780521424264.
2. Bollobas, B.; Erdös, P. (noviembre de 1976), "Cliques in random Graphs", Mathematical Proceedings of the Cambridge Philosophical Society , 80 (3): 419–427, Bibcode :1976MPCPS..80..419B, doi :10.1017/S0305004100053056, ISSN  1469-8064, S2CID  16619643
3. Kučera, Luděk (1995), "Complejidad esperada de los problemas de partición de gráficos", Matemáticas aplicadas discretas , 57 (2–3): 193–212, doi :10.1016/0166-218X(94)00103-K, hdl : 11858/ 00-001M-0000-0014-B73F-2 , SEÑOR  1327775.
4. Alón, Noga ; Krivelevich, Michael ; Sudakov, Benny (1998), "Encontrar una gran camarilla oculta en un gráfico aleatorio", Estructuras y algoritmos aleatorios , 13 (3–4): 457–466, CiteSeerX 10.1.1.24.6419 , doi :10.1002/(SICI)1098 -2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K, SEÑOR  1662795 
5. Feige, U .; Krauthgamer, R. (2000), "Encontrar y certificar una gran camarilla oculta en un gráfico semialeatorio", Algoritmos y estructuras aleatorias , 16 (2): 195–208, doi :10.1002/(SICI)1098-2418(200003)16 :2<195::AID-RSA5>3.0.CO;2-A.
6. Dekel, Yael; Gurel-Gurevich, Ori; Peres, Yuval (2014), "Encontrar camarillas ocultas en tiempo lineal con alta probabilidad", Combinatoria, probabilidad y computación , 23 (1): 29–49, arXiv : 1010.2997 , doi : 10.1017/S096354831300045X, MR  3197965, S2CID  14356678.
7. Hazán, Elad; Krauthgamer, Robert (2011), "¿Qué tan difícil es aproximarse al mejor equilibrio de Nash?", SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi :10.1137/090766991, MR  2765712 .
8. Grimmett, GR ; McDiarmid, CJH (1975), "Sobre colorear gráficos aleatorios", Procedimientos matemáticos de la Sociedad Filosófica de Cambridge , 77 (2): 313–324, Bibcode :1975MPCPS..77..313G, doi :10.1017/S0305004100051124, MR  0369129, S2CID  3421302.
9. Hombre valiente, Mark; Ko, joven Kun; Rubinstein, Aviad; Weinstein, Omri (2015), Dureza ETH para el subgrafo k más denso con perfecta integridad , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B.
10. Alón, Noga ; Andoni, Alejandro; Kaufman, Tali ; Matulef, Kevin; Rubinfeld, Ronitt ; Xie, Ning (2007), "Probando la independencia k -wise y casi k -wise", STOC'07 — Actas del 39º Simposio anual de ACM sobre teoría de la informática , Nueva York: ACM, págs. 496–505, doi :10.1145 /1250790.1250863, ISBN 9781595936318, SEÑOR  2402475, S2CID  5050980.
11. Balcan, María-Florina ; Borgs, cristiano; Braverman, Marcos; Chayés, Jennifer ; Teng, Shang-Hua (2013), "Encontrar comunidades formadas endógenamente", Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos (SODA '13) , SIAM, págs. 767–783, ISBN 978-1-611972-51-1.
12. Berthet, Quintín; Rigollet, Philippe (2013), "Límites inferiores teóricos de complejidad para la detección de componentes principales dispersos", Conferencia sobre teoría del aprendizaje, Journal of Machine Learning Research , 30 : 1046–1066.