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 subgráficos completos ) en un gráfico . Tiene varias formulaciones diferentes dependiendo de qué camarillas y qué información sobre las camarillas se debe 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 agrandar) y resolver el problema de decisión de probar si un gráfico contiene una camarilla más grande que un tamaño dado.
El problema de la camarilla surge en el siguiente entorno del mundo real. Considere una red social , donde los vértices del gráfico representan personas, y los bordes del gráfico representan un conocimiento mutuo. Entonces, una camarilla representa un subconjunto de personas que se conocen entre sí, y los algoritmos para encontrar camarillas se pueden usar 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 , química computacional y segmentación del movimiento [1] .
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 de Karp-NP completo ). El problema de encontrar la camarilla máxima es a la vez intratable de 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 exponencialmente muchas camarillas máximas. Por lo tanto, gran parte de la teoría sobre el problema de la camarilla se dedica a identificar tipos especiales de gráficos que admiten algoritmos más eficientes, o al establecimiento de la dificultad computacional del problema general en varios modelos de computación.
Para encontrar una camarilla máxima, uno puede inspeccionar sistemáticamente todos los subconjuntos, pero este tipo de búsqueda de fuerza bruta lleva 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 Bron-Kerbosch se puede usar para enumerar todas las camarillas máximas en el peor de los casos, y también es posible enumerarlas en tiempo polinómico por camarilla.
Historia y aplicaciones [ editar ]
El estudio de subgrafías completas en matemáticas es anterior a la terminología de "camarilla". Por ejemplo, las subgrafías completas hacen una aparición temprana en la literatura matemática en la reformulación teórica de grafos de la teoría de Ramsey por Erdős y Szekeres (1935) . Pero el término "camarilla" y el problema de enumerar algorítmicamente camarillas provienen de las ciencias sociales, donde se utilizan subgrafías completas 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 gráficos. Fueron los primeros en llamar a las subgrafías completas "camarillas". El primer algoritmo para resolver el problema de la camarilla es el de Harary &, [2] quienes fueron motivados por la aplicación sociológica. Los investigadores de ciencias sociales también han definido varios otros tipos de camarillas y camarillas máximas en las redes sociales, "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 representan pares de actores relacionados de la red social, y luego aplicando un algoritmo para el problema de la camarilla a este gráfico. [3]
Desde el trabajo de Harary y Ross, muchos otros han ideado algoritmos para varias versiones del problema de la camarilla. [2] En la década de 1970, los investigadores comenzaron a estudiar estos algoritmos desde el punto de vista del análisis del peor de los casos . Véase, por ejemplo, Tarjan y Trojanowski (1977) , un trabajo temprano sobre la complejidad del peor caso del problema de la camarilla máxima. También en la década de 1970, comenzando con el trabajo de Cook (1971) y Karp (1972) , los investigadores comenzaron a utilizar la teoría de la integridad de NP y los resultados de intractabilidad relacionados para proporcionar una explicación matemática de la dificultad percibida del problema de la camarilla. En la década de 1990, una serie de documentos innovadores que comienzan conFeige y col. (1991) y publicado en The New York Times , [4] mostró que (suponiendo P ≠ NP ) ni siquiera es posible aproximar el problema de manera precisa y eficiente.
Los algoritmos de búsqueda de camarillas se han utilizado en química , para encontrar productos químicos que coincidan con una estructura objetivo [5] y para modelar el acoplamiento molecular y los sitios de unión de las reacciones químicas. [6] También se pueden usar para encontrar estructuras similares dentro de diferentes moléculas. [7] En estas aplicaciones, uno forma un gráfico en el que cada vértice representa un par de átomos coincidentes, uno de cada una de las dos moléculas. Dos vértices están conectados por un borde si las coincidencias que representan son compatibles entre sí. Ser compatible puede significar, por ejemplo, que las distancias entre los átomos dentro de las dos moléculas son aproximadamente iguales, dentro de cierta tolerancia dada. Una camarilla en este gráfico representa un conjunto de pares de átomos coincidentes en los que todas las coincidencias son compatibles entre sí. [8] Un caso especial de este método es el uso del producto modular de gráficos para reducir el problema de encontrar el subgráfico inducido máximo común de dos gráficos al problema de encontrar una camarilla máxima en su producto. [9]
En la generación automática de patrones de prueba , encontrar camarillas puede ayudar a limitar el tamaño de un conjunto de prueba. [10] En bioinformática , se han utilizado algoritmos de búsqueda de camarillas para inferir árboles evolutivos , [11] predecir estructuras de proteínas , [12] y encontrar grupos de proteínas que interactúan estrechamente. [13] Listar las camarillas en un gráfico de dependencia es un paso importante en el análisis de ciertos procesos aleatorios. [14] En matemáticas, Lagarias y Shor (1992) refutaron la conjetura de Keller sobre el embaldosado cara a cara de los hipercubos ., que utilizó un algoritmo de búsqueda de camarillas en un gráfico asociado para encontrar un contraejemplo. [15]
Definiciones [ editar ]
Un gráfico no dirigido está formado por un conjunto finito de vértices y un conjunto de pares de vértices desordenados , que se denominan aristas . Por convención, en el análisis de algoritmos, el número de vértices en el gráfico se denota por n y el número de aristas se denota por m . A clique en una gráfica G es una completa subgrafo de G . Es decir, que es un subconjunto K de los vértices de tal manera que cada dos vértices en K son los dos puntos extremos de un borde en G . Una camarilla máximaes una camarilla a la que no se pueden agregar más vértices. Para cada vértice v que no es parte de una camarilla máxima, debe haber otro vértice w que esté en la camarilla y no sea adyacente a v , evitando que se agregue v a la camarilla. Una camarilla máxima es una camarilla que incluye el mayor número posible de vértices. El número clique ω ( G ) es el número de vértices en una camarilla máximo de G . [2]
Se han estudiado varios problemas relacionados con la búsqueda de camarillas. [dieciséis]
- En el problema de la camarilla máxima, la entrada es un gráfico no dirigido y la salida es una camarilla máxima en el gráfico. Si hay varias camarillas máximas, una de ellas puede elegirse arbitrariamente. [dieciséis]
- En el problema de la camarilla máxima ponderada, la entrada es un gráfico no dirigido con pesos en sus vértices (o, con menos frecuencia, bordes) y la salida es una camarilla con el peso total máximo. El problema de la camarilla máxima es el caso especial en el que todos los pesos son iguales. [17] Además del problema de optimizar la suma de los pesos, también se han estudiado otros problemas de optimización de bicriterios más complicados. [18]
- En el problema de listado máximo de camarillas, la entrada es un gráfico no dirigido y el resultado es una lista de todas sus camarillas máximas. El problema de la camarilla máxima se puede resolver utilizando como subrutina un algoritmo para el problema de listado máximo de camarillas, porque la camarilla máxima debe incluirse entre todas las camarillas máximas. [19]
- En el problema k -clique, la entrada es un gráfico no dirigido y un número k . La salida es una camarilla con k vértices, si existe, o un valor especial que indica que no hay k- camarilla de lo contrario. En algunas variaciones de este problema, la salida debe enumerar todas las camarillas de tamaño k . [20]
- En el problema de decisión de la camarilla, la entrada es un gráfico no dirigido y un número k , y la salida es un valor booleano : verdadero si el gráfico contiene una k -clique, y falso en caso contrario. [21]
Los primeros cuatro de estos problemas son importantes en aplicaciones prácticas. El problema de decisión de la camarilla no es de importancia práctica; está formulado de esta manera para aplicar la teoría de la completitud NP a los problemas de búsqueda de camarillas. [21]
El problema de la camarilla y el problema del conjunto independiente son complementarios: una camarilla en G es un conjunto independiente en el gráfico complementario de G y viceversa. [22] Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los problemas, y algunos trabajos de investigación no distinguen claramente entre los dos problemas. Sin embargo, los dos problemas tienen propiedades diferentes cuando se aplican a familias restringidas de gráficos. Por ejemplo, el problema de la camarilla puede resolverse en tiempo polinómico para gráficos planos [23], mientras que el problema del conjunto independiente sigue siendo NP-duro en los gráficos planos. [24]
Algoritmos [ editar ]
Encontrar una sola camarilla máxima [ editar ]
Una camarilla máxima , a veces llamada inclusión-máxima, es una camarilla que no está incluida en una camarilla más grande. Por lo tanto, cada camarilla está contenida en una camarilla máxima. [25] Las camarillas máximas pueden ser muy pequeñas. Un gráfico puede contener una camarilla no máxima con muchos vértices y una camarilla separada de tamaño 2 que es máxima. Mientras que una camarilla máxima (es decir, la más grande) es necesariamente máxima, lo contrario no se cumple. Hay algunos tipos de gráficos en los que cada camarilla máxima es máxima; Estos son los complementos de los gráficos bien cubiertos , en los que cada conjunto independiente máximo es máximo. [26] Sin embargo, otros gráficos tienen camarillas máximas que no son máximas.
Un único algoritmo codicioso puede encontrar una única camarilla máxima . Comenzando con una camarilla arbitraria (por ejemplo, cualquier vértice único o incluso el conjunto vacío), haga crecer la camarilla actual un vértice a la vez recorriendo los vértices restantes del gráfico. Para cada vértice v que examina este bucle, agregue v a la camarilla si está adyacente a cada vértice que ya está en la camarilla, y descarte v de lo contrario. Este algoritmo se ejecuta en tiempo lineal . [27] Debido a la facilidad de encontrar camarillas máximas, y su pequeño tamaño potencial, se ha prestado más atención al problema algorítmico mucho más difícil de encontrar una camarilla máxima o grande que el problema de encontrar una camarilla máxima única. Sin embargo, algunas investigaciones en algoritmos paralelos han estudiado el problema de encontrar una camarilla máxima. En particular, se ha demostrado que el problema de encontrar la primera camarilla máxima lexicográficamente (la encontrada por el algoritmo anterior) es completa para la clase de funciones de tiempo polinomial . Este resultado implica que es poco probable que el problema pueda resolverse dentro de la clase de complejidad paralela NC . [28]
Camarillas de tamaño fijo [ editar ]
Uno puede probar si una gráfica G contiene una camarilla k- vértice, y encontrar cualquier camarilla que contenga, utilizando un algoritmo de fuerza bruta . Este algoritmo examina cada subgrafo con k vértices y verifica si forma una camarilla. Lleva tiempo O ( n k k 2 ) , como se expresa usando la notación O grande . Esto se debe a que hay O ( n k ) subgrafías para verificar, cada una de las cuales tiene bordes O ( k 2 ) cuya presencia en Gnecesita ser revisado Por lo tanto, el problema puede resolverse en tiempo polinómico siempre que k sea una constante fija. Sin embargo, cuando k no tiene un valor fijo, sino que puede variar como parte de la entrada al problema, el tiempo es exponencial. [29]
El caso no trivial más simple del problema de búsqueda de camarillas es encontrar un triángulo en un gráfico, o determinar de manera equivalente si el gráfico está libre de triángulos . En un gráfico G con m aristas, puede haber como máximo triángulos Θ ( m 3/2 ) (usando la notación theta grande para indicar que este límite es estrecho). El peor caso para esta fórmula ocurre cuando G es en sí mismo una camarilla. Por lo tanto, los algoritmos para enumerar todos los triángulos deben tomar al menos Ω ( m 3/2 ) en el peor de los casos (usando notación omega grande ), y se sabe que los algoritmos coinciden con este límite de tiempo. [30]Por ejemplo, Chiba y Nishizeki (1985) describen un algoritmo que ordena los vértices en orden de mayor a menor y luego itera a través de cada vértice v en la lista ordenada, buscando triángulos que incluyan v y no incluyan ningún vértice previo en el lista. Para hacerlo, el algoritmo marca a todos los vecinos de v , busca a través de todos los bordes incidentes con un vecino de v generando un triángulo para cada borde que tiene dos puntos finales marcados, y luego elimina las marcas y elimina v del gráfico. Como muestran los autores, el tiempo para este algoritmo es proporcional a la arboricidad del gráfico (denotado como ( G )) multiplicado por el número de aristas, que es O ( m a ( G )) . Como la arboricidad es como máximo O ( m 1/2 ) , este algoritmo se ejecuta en el tiempo O ( m 3/2 ) . Más generalmente, todos los k camarillas -vertex pueden ser enumerados mediante un algoritmo similar que toma tiempo proporcional al número de bordes multiplicado por el arboricity a la potencia ( k - 2) . Para los gráficos de arboricidad constante, como los gráficos planos (o en gráficos generales de cualquier familia de gráficos cerrada menor no trivial ), este algoritmo toma O( m ) tiempo, que es óptimo ya que es lineal en el tamaño de la entrada. [20]
Si uno desea solo un triángulo único, o una garantía de que el gráfico no tiene triángulos, son posibles algoritmos más rápidos. Como observan Itai y Rodeh (1978) , el gráfico contiene un triángulo si y solo si su matriz de adyacencia y el cuadrado de la matriz de adyacencia contienen entradas distintas de cero en la misma celda. Por lo tanto, se pueden aplicar técnicas rápidas de multiplicación de matrices, como el algoritmo Coppersmith – Winograd para encontrar triángulos en el tiempo O ( n 2.376 ) . Alon, Yuster y Zwick (1994) usaron la multiplicación de matriz rápida para mejorar el algoritmo O ( m 3/2 ) para encontrar triángulos a O( m 1,41 ) . Estos algoritmos basados en la multiplicación rápida de matrices también se han extendido a problemas de encontrar k- cliques para valores más grandes de k . [31]
Listado de todas las camarillas máximas [ editar ]
Como resultado de Moon & Moser (1965) , cada gráfico de n -vértices tiene como máximo 3 n / 3 camarillas máximas. Se pueden enumerar mediante el algoritmo Bron-Kerbosch , un procedimiento de retroceso recursivo de Bron & Kerbosch (1973). La subrutina recursiva principal de este procedimiento tiene tres argumentos: una camarilla parcialmente construida (no máxima), un conjunto de vértices candidatos que podrían agregarse a la camarilla y otro conjunto de vértices que no deberían agregarse (porque hacerlo conduciría a una camarilla que ya se ha encontrado). El algoritmo intenta agregar los vértices candidatos uno por uno a la camarilla parcial, haciendo una llamada recursiva para cada uno. Después de probar cada uno de estos vértices, lo mueve al conjunto de vértices que no se deben agregar nuevamente. Se puede demostrar que las variantes de este algoritmo tienen el peor tiempo de ejecución O (3 n / 3 ) , coincidiendo con el número de camarillas que podrían necesitar ser enumeradas. [32]Por lo tanto, esto proporciona una solución óptima para el peor de los casos al problema de enumerar todas las camarillas máximas. Además, se ha informado ampliamente que el algoritmo Bron-Kerbosch es más rápido en la práctica que sus alternativas. [33]
Sin embargo, cuando el número de camarillas es significativamente menor que su peor caso, otros algoritmos podrían ser preferibles. Como Tsukiyama et al. (1977) mostraron que también es posible enumerar todas las camarillas máximas en un gráfico en una cantidad de tiempo que es polinomial por camarilla generada. Un algoritmo como el suyo en el que el tiempo de ejecución depende del tamaño de salida se conoce como algoritmo sensible a la salida . Su algoritmo se basa en las siguientes dos observaciones, que relacionan las camarillas máximas del gráfico G dado con las camarillas máximas de un gráfico G \ v formado al eliminar un vértice arbitrario v de G :
- Por cada máximo clique K de G \ v , o bien K continúa para formar una camarilla máxima en G , o K ⋃ { v } forma un camarilla máxima en G . Por lo tanto, G tiene al menos tantas camarillas máximas como G \ v .
- Cada camarilla máxima en G que no contiene v es una camarilla máxima en G \ v , y cada camarilla máxima en G que contiene v puede formarse a partir de una camarilla máxima K en G \ v agregando v y eliminando los no vecinos de v de K .
Usando estas observaciones, pueden generar todas las camarillas máximas en G mediante un algoritmo recursivo que elige un vértice v arbitrariamente y luego, para cada camarilla máxima K en G \ v , genera tanto K como la camarilla formada al agregar v a K y eliminar el no -vecinos de v . Sin embargo, algunas camarillas de G pueden generarse de esta manera desde más de una camarilla principal de G \ v , por lo que eliminan los duplicados al generar una camarilla en G solo cuando su padre en G \ ves lexicográficamente máximo entre todas las posibles camarillas de padres. Sobre la base de este principio, que muestran que todas las camarillas máxima en G pueden ser generados en el tiempo O ( mn ) por camarilla, donde m es el número de aristas en G y n es el número de vértices. Chiba y Nishizeki (1985) mejoran esto a O ( ma ) por camarilla, donde a es la arboricidad del gráfico dado. Makino y Uno (2004) proporcionan un algoritmo alternativo sensible a la salida basado en la multiplicación rápida de matrices. Johnson y Yannakakis (1988)Demuestre que incluso es posible enumerar todas las camarillas máximas en orden lexicográfico con retraso polinómico por camarilla. Sin embargo, la elección del orden es importante para la eficiencia de este algoritmo: para el reverso de este orden, no existe un algoritmo de retraso polinómico a menos que P = NP .
Sobre la base de este resultado, es posible enumerar todas las camarillas máximas en tiempo polinómico, para familias de gráficos en los que el número de camarillas está polinomialmente limitado. Estas familias incluyen gráficos de cuerdas , gráficos completos , gráficos libre de triángulo , grafo de intervalos , gráficos de acotada boxicity , y grafos planos . [34] En particular, los gráficos planos tienen camarillas O ( n ) , de tamaño máximo como máximo, que se pueden enumerar en tiempo lineal. Lo mismo es cierto para cualquier familia de gráficos que sea escasa (con un número de aristas como máximo constante por el número de vértices) ycerrado bajo la operación de tomar subgrafos. [20] [35]
Encontrar camarillas máximas en gráficos arbitrarios [ editar ]
Es posible encontrar la camarilla máxima, o el número de camarilla, de un gráfico de n- vértices arbitrario en el tiempo O (3 n / 3 ) = O (1.4422 n ) utilizando uno de los algoritmos descritos anteriormente para enumerar todas las camarillas máximas en el gráfico y devolviendo el más grande. Sin embargo, para esta variante del problema de la camarilla son posibles mejores límites de tiempo en el peor de los casos. El algoritmo de Tarjan y Trojanowski (1977) resuelve este problema en el tiempo O (2 n / 3 ) = O (1.2599 n ) . Es un esquema de retroceso recursivo similar al del algoritmo Bron-Kerbosch., pero puede eliminar algunas llamadas recursivas cuando se puede demostrar que las camarillas encontradas dentro de la llamada serán subóptimas. Jian (1986) mejoró el tiempo a O (2 0.304 n ) = O (1.2346 n ) , y Robson (1986) lo mejoró a O (2 0.276 n ) = O (1.2108 n ) tiempo, a expensas de un mayor uso del espacio . El algoritmo de Robson combina un esquema de retroceso similar (con un análisis de caso más complicado) y una técnica de programación dinámica en la que la solución óptima se calcula previamente para todas las pequeñas subgrafías conectadas delgrafo complemento . Estas soluciones parciales se utilizan para atajar la recursividad de retroceso. El algoritmo más rápido conocido hoy es una versión refinada de este método por Robson (2001) que se ejecuta en el tiempo O (2 0.249 n ) = O (1.1888 n ) . [36]
También se ha realizado una amplia investigación sobre algoritmos heurísticos para resolver problemas de camarilla máxima sin garantías de tiempo de ejecución en el peor de los casos, basados en métodos que incluyen ramificación y enlace , [37] búsqueda local , [38] algoritmos codiciosos , [39] y programación de restricciones . [40] Las metodologías de computación no estándar que se han sugerido para encontrar camarillas incluyen la computación de ADN [41] y la computación cuántica adiabática . [42] El problema de la camarilla máxima fue el tema de un desafío de implementación patrocinado por DIMACS en 1992-1993,[43] y una colección de gráficos utilizados como puntos de referencia para el desafío, que está a disposición del público.
No hay comentarios:
Publicar un comentario