Camarilla plantada

Complete subgraph added to a random graph

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

En la teoría de la complejidad computacional , una camarilla plantada o camarilla oculta en un grafo no dirigido es una camarilla formada a partir de otro grafo 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 grafos aleatorios de grafos que tienen una camarilla plantada. Esta es una variación del problema de la camarilla ; puede resolverse en tiempo cuasi-polinomial pero se conjetura que no es solucionable en tiempo polinomial para valores intermedios del tamaño de la camarilla. La conjetura de que no existe una solución en tiempo 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 ellos adyacentes entre sí. Una camarilla plantada es una camarilla creada a partir de otro gráfico mediante la adición de 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 grafos, parametrizados 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 grafo, mediante el siguiente proceso aleatorio: ^[1]

1. Cree un gráfico aleatorio de Erdős–Rényi en n vértices eligiendo independientemente para cada par de vértices si desea incluir una arista 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, devuelve 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) entre cada par de vértices seleccionados.

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

Límites superior e inferior

Existe una función tal que, de manera casi segura y asintótica, el tamaño de la camarilla más grande en un grafo aleatorio de n vértices es o bien , ^[2] y existe alguna constante tal que el número esperado de camarillas de tamaño converge a infinito. En consecuencia, se debería esperar que la plantación de una camarilla 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 de , se crearía un cambio detectable en la forma de la distribución. Es decir, si se traza la distribución de los grados de los vértices, parecería una curva de campana deformada. Por lo tanto, el rango de valores más interesante para el parámetro k está 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 polinomial. ^[1]

Kučera (1995) observa que, cuando es casi seguro que 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 es posible encontrar una camarilla plantada con alta probabilidad mediante el siguiente método: ${\displaystyle k>10{\sqrt {n}}}$

1. Calcular 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 que son adyacentes a al menos 3/4 de los vértices seleccionados.

Muestran cómo modificar esta técnica para que siga 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 el 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 tiempo cuasi-polinomial . ^[7] Debido a que la camarilla más grande en un gráfico aleatorio normalmente 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. Realizar un bucle a través de todos los conjuntos S de vértices. ${\displaystyle \min(k,3\log _{2}n)}$
2. Para cada opción de S , prueba si S es una camarilla. Si lo es, y , devuelve S . De lo contrario, encuentra 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 cuasipolinómico, porque hay cuasipolinómicamente muchas opciones de S para recorrer. Se garantiza que este método probará un conjunto S que sea un subconjunto del grupo seleccionado; con alta probabilidad, el conjunto T estará formado únicamente por otros miembros del grupo seleccionado.

Como suposición de dureza

Existen dos versiones de la conjetura de la camarilla plantada: una basada en encontrar la camarilla (búsqueda) y otra basada en determinar si existe una camarilla (decisión). La conjetura de búsqueda establece que ningún algoritmo de tiempo polinomial puede encontrar (con alta probabilidad) una camarilla oculta de tamaño << en un grafo aleatorio con nodos. ^[9] ${\displaystyle k}$ ${\displaystyle n^{0.5}}$ ${\displaystyle n}$

La conjetura de decisión es más sutil. Supongamos que se nos dan dos grafos aleatorios de nodos, exactamente uno de los cuales tiene una camarilla plantada, pero no sabemos cuál. En promedio, un grafo aleatorio con una camarilla plantada tendrá más aristas que un grafo puramente aleatorio, ya que se espera que el acto de plantar una camarilla de tamaño agregue aristas. Por lo tanto, podemos determinar correctamente cuál de los dos grafos contiene la camarilla plantada con probabilidad simplemente contando el número de aristas en cada grafo. La conjetura de decisión de la camarilla plantada establece que esto es esencialmente óptimo: postula que ningún algoritmo de tiempo polinomial puede distinguir entre los dos grafos con probabilidad mayor que . ^{[9] [10]} ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \Theta (k^{2})}$ ${\displaystyle 1/2+\Theta (k^{2}/n)}$ ${\displaystyle 1/2+\Theta (k^{2}/n)}$

Hazan y Krauthgamer (2011) utilizaron el supuesto de que encontrar camarillas plantadas es difícil como un supuesto de dificultad computacional para demostrar que, si es 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 dificultad para mostrar la dificultad de probar la propiedad de la k -independencia de distribuciones aleatorias, ^[11] encontrar grupos en redes sociales, ^[12] y aprendizaje automático . ^[13]

Referencias

1. Arora, 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), "Camarillas en grafos aleatorios", 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 problemas de partición de grafos", Discrete Applied Mathematics , 57 (2–3): 193–212, doi :10.1016/0166-218X(94)00103-K, hdl : 11858/00-001M-0000-0014-B73F-2 , MR  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 camarilla oculta grande en un gráfico semialeatorio", Random Structures and Algorithms , 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", Combinatorics, Probability and Computing , 23 (1): 29–49, arXiv : 1010.2997 , doi :10.1017/S096354831300045X, MR  3197965, S2CID  14356678.
7. Hazan, 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 la coloración de gráficos aleatorios", Mathematical Proceedings of the Cambridge Philosophical Society , 77 (2): 313–324, Bibcode :1975MPCPS..77..313G, doi :10.1017/S0305004100051124, MR  0369129, S2CID  3421302.
9. Hirahara, Shuichi; Shimizu, Nobutaka (2024), "Las conjeturas de camarilla plantadas son equivalentes", Actas del 56.º Simposio anual de la ACM sobre teoría de la computación , págs. 358-366, doi : 10.1145/3618260.3649751 , ISBN 979-8-4007-0383-6
10. Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), Dureza ETH para el subgrafo k más denso con completitud perfecta , arXiv : 1504.08352 , Bibcode :2015arXiv150408352B.
11. Alon, Noga ; Andoni, Alexandr; Kaufman, Tali ; Matulef, Kevin; Rubinfeld, Ronitt ; Xie, Ning (2007), "Prueba de independencia en función de k y casi en función de k ", STOC'07—Actas del 39.° Simposio Anual de la ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 496–505, doi :10.1145/1250790.1250863, ISBN 9781595936318, MR  2402475, S2CID  5050980.
12. Balcan, Maria-Florina ; Borgs, Christian; Braverman, Mark; Chayes, 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.
13. Berthet, Quentin; 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.