En la teoría de la complejidad computacional , una camarilla plantada o camarilla oculta en un gráfico no dirigido es una camarilla formada a partir de otro gráfico al seleccionar un subconjunto de vértices y agregar 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 ; se puede resolver en tiempo cuasi-polinomial pero se conjetura que no se puede resolver en tiempo polinomialpara valores intermedios del tamaño de la camarilla. La conjetura de que no existe una solución de tiempo polinomial se llama conjetura de 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 al agregar bordes entre todos los pares de un subconjunto seleccionado de vértices.
El problema de la camarilla plantada puede formalizarse 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) yk (el tamaño de la camarilla). Estos parámetros se pueden utilizar para generar un gráfico mediante el siguiente proceso aleatorio: [1]
- Cree un gráfico aleatorio de Erdős-Rényi en n vértices eligiendo independientemente para cada par de vértices si incluir una arista que conecte ese par, con probabilidad 1/2 para cada par.
- Decida si agregar o no un grupo al gráfico, con probabilidad 1/2; si no, devuelva el gráfico formado en el paso 1.
- Elija aleatoriamente un subconjunto de k de los n vértices y agregue un borde (si no hay uno ya presente) entre cada par de los vértices seleccionados.
El problema es entonces determinar algorítmicamente si una de las gráficas resultantes de este proceso contiene una camarilla de al menos k vértices.
Con alta probabilidad, el tamaño de la camarilla más grande en un gráfico aleatorio de n -vértices es cercano a 2 log 2 n . Y cuando k es mayor que la raíz cuadrada de n , se puede reconocer que los vértices de una camarilla plantada tienen grados inusualmente grandes , lo que hace que una camarilla plantada sea fácil de encontrar. Por tanto, el rango de valores más interesante para el parámetro k se encuentra entre estos dos valores, [1]
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, cuandoentonces 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 vértice sean más uniformes incluso para valores grandes de k , pero muestra que, a pesar de esta modificación, la camarilla plantada todavía se puede encontrar rápidamente. [2]
Alon, Krivelevich y Sudakov (1998) prueban una camarilla plantada se puede encontrar con alta probabilidad mediante el siguiente método:
- Calcule el vector propio de la matriz de adyacencia correspondiente a su segundo valor propio más alto .
- Seleccione los k vértices cuyas coordenadas en este vector propio tienen los valores absolutos más grandes .
- 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. [3] También se pueden encontrar grandes camarillas plantadas usando programación semidefinida . [4] Una técnica combinatoria basada en el muestreo aleatorio de vértices puede lograr el mismo límite en ky se ejecuta en tiempo lineal . [5]
Tiempo cuasipolinomial
También es posible resolver el problema de la camarilla plantada, independientemente de la elección de k , en un tiempo cuasi polinomial . [6] Debido a que la camarilla más grande en un gráfico aleatorio generalmente tiene un tamaño cercano a 2 log 2 n , [7] una camarilla plantada de tamaño k (si existe) se puede encontrar con alta probabilidad mediante el siguiente método:
- Recorra todos los conjuntos S de vértices.
- Para cada elección de S , pruebe si S es una camarilla. Si lo es, y, Volver S . De lo contrario, encontrar el conjunto T de vértices que son adyacentes a todos los vértices en S . Si, Volver T .
El tiempo de ejecución de este algoritmo es cuasipolinomial, porque hay cuasipolinomialmente muchas opciones de S para realizar un bucle. Este método está garantizado para probar un conjunto S que es un subconjunto de la camarilla plantada; con alta probabilidad, el conjunto T consistirá sólo en otros miembros de la camarilla plantada.
Como suposición de dureza
La conjetura de la camarilla plantada es la conjetura de que no existe un algoritmo de tiempo polinomial que tome como entrada los gráficos producidos por el proceso de la camarilla plantada y distinga a los que tienen camarillas plantadas de los que no tienen camarillas plantadas con una probabilidad significativamente mejor que el azar. [8]
Hazan y Krauthgamer (2011) utilizaron el supuesto de que encontrar camarillas plantadas es difícil como un supuesto de dureza computacional para demostrar que, de ser así, también es difícil aproximar el mejor equilibrio de Nash en un juego de dos jugadores. [6] 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, [9] encontrar clústeres en redes sociales, [10] y aprendizaje automático . [11]
Referencias
- ^ a b c Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, págs. 362–363, ISBN 9780521424264.
- ^ Kučera, Luděk (1995), "La 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 , MR 1327775.
- ^ Alon, 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 (12 de octubre de 1998) 13: 3/4 <457 :: AID-RSA14> 3.3.CO; 2-K , MR 1662795
- ^ Feige, U .; Krauthgamer, R. (2000), "Encontrar y certificar una gran camarilla oculta en un gráfico semialeatorio", Estructuras y algoritmos aleatorios , 16 (2): 195-208, doi : 10.1002 / (SICI) 1098-2418 (200003) 16 : 2 <195 :: AID-RSA5> 3.0.CO; 2-A.
- ^ 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.
- ^ a b Hazan, Elad; Krauthgamer, Robert (2011), "¿Qué tan difícil es aproximar el mejor equilibrio de Nash?", SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi : 10.1137 / 090766991 , MR 2765712.
- ^ Grimmett, GR ; McDiarmid, CJH (1975), "Sobre la coloración de gráficos aleatorios", Actas de matemáticas de la Sociedad Filosófica de Cambridge , 77 (2): 313–324, Código Bibliográfico : 1975MPCPS..77..313G , doi : 10.1017 / S0305004100051124 , MR 0369129.
- ^ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), Dureza ETH para el subgráfico k más denso con perfecta integridad , arXiv : 1504.08352 , Bibcode : 2015arXiv150408352B.
- ^ Alon, Noga ; Andoni, Alexandr; Kaufman, Tali; Matulef, Kevin; Rubinfeld, Ronitt; Xie, Ning (2007), "Testing k -wise and casi k -wise independent", STOC'07 - Actas del 39º Simposio Anual de ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 496–505, doi : 10.1145 /1250790.1250863 , ISBN 9781595936318, MR 2402475.
- ^ 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.
- ^ Berthet, Quentin; Rigollet, Philippe (2013), "Límites inferiores teóricos de la complejidad para la detección de componentes principales dispersos" , Conferencia sobre teoría del aprendizaje, Journal of Machine Learning Research , 30 : 1046–1066.