Problema de camarilla
En informática , el problema de la camarilla es el problema computacional de encontrar camarillas (subconjuntos de vértices, todos adyacentes entre sí, también llamados subgrafos completos ) en un gráfico . Tiene varias formulaciones diferentes según las camarillas y la información sobre las camarillas que se deben encontrar. Las formulaciones comunes del problema de la camarilla incluyen encontrar una camarilla máxima (una camarilla con el mayor número posible de vértices), encontrar una camarilla de peso máximo en un gráfico ponderado, enumerar todas las camarillas máximas (camarillas que no se pueden ampliar) y resolver el problema de decisión. de probar si un gráfico contiene un grupo más grande que un tamaño dado.
El problema de la camarilla surge en el siguiente escenario del mundo real. Considere una red social , donde los vértices del gráfico representan personas y los bordes del gráfico representan conocimiento mutuo. Luego, una camarilla representa un subconjunto de personas que se conocen entre sí, y se pueden usar algoritmos para encontrar camarillas para descubrir estos grupos de amigos mutuos. Junto con sus aplicaciones en las redes sociales, el problema de la camarilla también tiene muchas aplicaciones en bioinformática y química computacional .
La mayoría de las versiones del problema de la camarilla son difíciles. El problema de decisión de la camarilla es NP-completo (uno de los 21 problemas NP-completo de Karp ). El problema de encontrar la camarilla máxima es a la vez intratable con parámetros fijos y difícil de aproximar . Y, enumerar todas las camarillas máximas puede requerir un tiempo exponencial, ya que existen gráficos con muchas camarillas máximas exponencialmente. Por lo tanto, gran parte de la teoría sobre el problema de la camarilla está dedicada a identificar tipos especiales de grafos que admiten algoritmos más eficientes, o a establecer la dificultad computacional del problema general en varios modelos de computación.
Para encontrar una camarilla máxima, se pueden inspeccionar sistemáticamente todos los subconjuntos, pero este tipo de búsqueda de fuerza bruta requiere demasiado tiempo para ser práctico para redes que comprenden más de unas pocas docenas de vértices. Aunque no hay tiempo polinómico algoritmo es conocido por este problema, más eficientes algoritmos se conocen que la búsqueda de fuerza bruta. Por ejemplo, el algoritmo de Bron-Kerbosch se puede utilizar para enumerar todas las camarillas máximas en el momento óptimo en el peor de los casos, y también es posible enumerarlas en tiempo polinómico por camarilla.
El estudio de subgrafos completos en matemáticas es anterior a la terminología de "camarilla". Por ejemplo, los subgrafos completos hacen una aparición temprana en la literatura matemática en la reformulación de la teoría de grafos de la teoría de Ramsey por Erdős & Szekeres (1935) . Pero el término "camarilla" y el problema de enumerar camarillas algorítmicamente provienen de las ciencias sociales, donde se utilizan subgrafos completos para modelar camarillas sociales , grupos de personas que se conocen entre sí. Luce y Perry (1949) utilizaron gráficos para modelar redes sociales y adaptaron la terminología de las ciencias sociales a la teoría de grafos. Fueron los primeros en llamar "camarillas" a los subgrafos completos. El primer algoritmo para resolver el problema de la camarilla es el de Harary &Ross (1957), [1] quienes fueron motivados por la aplicación sociológica. Los investigadores de las ciencias sociales también han definido varios otros tipos de camarillas y camarillas máximas en la red social, "subgrupos cohesivos" de personas o actores en la red, todos los cuales comparten uno de varios tipos diferentes de relación de conectividad. Muchas de estas nociones generalizadas de camarillas también se pueden encontrar construyendo un gráfico no dirigido cuyos bordes representen pares relacionados de actores de la red social, y luego aplicando un algoritmo para el problema de camarillas a este gráfico. [2]
