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. Entonces, 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 un parámetro fijo intratable 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 polinomial por camarilla.
Historia y aplicaciones
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 y Ross (1957) , [1] quienes fueron motivados por la aplicación sociológica. Los investigadores en 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]
Desde el trabajo de Harary y Ross, muchos otros han ideado algoritmos para varias versiones del problema de la camarilla. [1] 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) , uno de los primeros trabajos sobre la complejidad del peor de los casos 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 NP-completitud y los resultados de intratabilidad 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 revolucionaria de artículos que comenzó con Feige et al. (1991) y publicado en The New York Times , [3] mostró que (asumiendo 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 sustancias químicas que coincidan con una estructura objetivo [4] y para modelar el acoplamiento molecular y los sitios de unión de las reacciones químicas. [5] También se pueden utilizar para encontrar estructuras similares dentro de diferentes moléculas. [6] En estas aplicaciones, se forma un gráfico en el que cada vértice representa un par de átomos emparejados, 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 una tolerancia dada. Una camarilla en este gráfico representa un conjunto de pares de átomos en los que todas las coincidencias son compatibles entre sí. [7] Un caso especial de este método es el uso del producto modular de gráficos para reducir el problema de encontrar el subgrafo inducido máximo común de dos gráficos al problema de encontrar un clique máximo en su producto. [8]
En la generación automática de patrones de prueba , encontrar camarillas puede ayudar a limitar el tamaño de un conjunto de prueba. [9] En bioinformática , se han utilizado algoritmos de búsqueda de camarillas para inferir árboles evolutivos , [10] predecir estructuras de proteínas , [11] y encontrar grupos de proteínas que interactúan estrechamente. [12] Enumerar las camarillas en un gráfico de dependencia es un paso importante en el análisis de ciertos procesos aleatorios. [13] En matemáticas, la conjetura de Keller sobre el mosaico cara a cara de hipercubos fue refutada por Lagarias y Shor (1992) , quienes utilizaron un algoritmo de búsqueda de camarillas en un gráfico asociado para encontrar un contraejemplo. [14]
Definiciones
Un grafo 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áxima es una camarilla a la que no se pueden agregar más vértices. Para cada vértice v que no sea parte de una camarilla máxima, debe haber otro vértice w que esté en la camarilla y no adyacente a v , evitando que v se agregue 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 . [1]
Se han estudiado varios problemas de búsqueda de camarillas estrechamente relacionados. [15]
- 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 múltiples camarillas máximas, una de ellas puede elegirse arbitrariamente. [15]
- En el problema de 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 peso total máximo. El problema de la camarilla máxima es el caso especial en el que todos los pesos son iguales. [16] Además del problema de optimizar la suma de pesos, también se han estudiado otros problemas de optimización de bicriterio más complicados. [17]
- En el problema de listado de camarillas máximas, la entrada es un gráfico no dirigido y la salida es una lista de todas sus camarillas máximas. El problema de la camarilla máxima puede resolverse utilizando como subrutina un algoritmo para el problema de la lista de la camarilla máxima, porque la camarilla máxima debe incluirse entre todas las camarillas máximas. [18]
- En el problema k -clique, la entrada es una gráfica no dirigida 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 -clique en caso contrario. En algunas variaciones de este problema, la salida debe enumerar todas las camarillas de tamaño k . [19]
- En el problema de decisión de 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 un k -clique y falso en caso contrario. [20]
Los primeros cuatro de estos problemas son importantes en aplicaciones prácticas. El problema de la decisión de la camarilla no es de importancia práctica; está formulado de esta manera para aplicar la teoría de NP-completitud a problemas de búsqueda de camarillas. [20]
El problema de la camarilla y el problema del conjunto independiente son complementarios: una camarilla en G es un conjunto independiente en la gráfica de complemento de G y viceversa. [21] Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquier problema, y algunos artículos 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 polinomial para gráficas planas [22] mientras que el problema de conjuntos independientes sigue siendo NP-hard en gráficas planas. [23]
Algoritmos
Encontrar una única camarilla máxima
Una camarilla máxima , a veces llamada de 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. [24] 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. Si bien 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 máximo independiente es máximo. [25] Sin embargo, otros gráficos tienen grupos máximos que no son máximos.
Se puede encontrar una única camarilla máxima mediante un sencillo algoritmo codicioso . Comenzando con una camarilla arbitraria (por ejemplo, cualquier vértice individual 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 al clique si está adyacente a todos los vértices que ya están en el clique, y descarte v en caso contrario. Este algoritmo se ejecuta en tiempo lineal . [26] Debido a la facilidad de encontrar camarillas máximas, y su tamaño potencial pequeño, se ha prestado más atención al problema algorítmico mucho más difícil de encontrar una camarilla máxima o grande. 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 que encuentra el algoritmo anterior) es completo para la clase de funciones de tiempo polinómico . Este resultado implica que es poco probable que el problema se pueda resolver dentro de la clase de complejidad paralela NC . [27]
Camarillas de tamaño fijo
Se puede probar si un gráfico G contiene una camarilla de k- vértices y encontrar cualquier camarilla que contenga, utilizando un algoritmo de fuerza bruta . Este algoritmo examina cada subgrafo con k vértices y comprueba si forma una camarilla. Se necesita tiempo O ( n k k 2 ) , como se expresa usando la notación O grande . Esto se debe a que hay subgrafos O ( n k ) para verificar, cada uno de los cuales tiene bordes O ( k 2 ) cuya presencia en G debe verificarse. Por tanto, el problema puede resolverse en tiempo polinomial 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. [28]
El caso no trivial más simple del problema de búsqueda de pandillas es encontrar un triángulo en una gráfica o, de manera equivalente, determinar si la gráfica no tiene triángulos . En un gráfico G con m aristas, puede haber como máximo Θ ( m 3/2 ) triángulos (usando una notación theta grande para indicar que este límite es estrecho). El peor de los casos 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 ) tiempo en el peor de los casos (usando una notación omega grande ), y se conocen algoritmos que coinciden con este límite de tiempo. [29] 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 en la lista. Para hacerlo, el algoritmo marca todos los vecinos de v , busca en todos los bordes incidentes a un vecino de v generando un triángulo para cada borde que tenga dos extremos marcados, y luego quita las marcas y borra v del gráfico. Como muestran los autores, el tiempo para este algoritmo es proporcional a la arboricidad del gráfico (denotado a ( G ) ) multiplicado por el número de aristas, que es O ( m a ( G )) . Dado que la arboricidad es como máximo O ( m 1/2 ) , este algoritmo se ejecuta en el tiempo O ( m 3/2 ) . De manera más general, todas las camarillas de k- vértices se pueden enumerar mediante un algoritmo similar que toma un tiempo proporcional al número de aristas multiplicado por la arboricidad a la potencia ( k - 2) . Para gráficos de arboricidad constante, como los gráficos planos (o en general los gráficos de cualquier familia de gráficos cerrados menores no triviales ), este algoritmo toma O ( m ) tiempo, que es óptimo ya que es lineal en el tamaño de la entrada. [19]
Si se desea un solo triángulo, o la seguridad de que el gráfico no tiene triángulos, es posible utilizar 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 de multiplicación de matrices rápidas, como el algoritmo Coppersmith-Winograd, para encontrar triángulos en el tiempo O ( n 2.376 ) . Alon, Yuster y Zwick (1994) utilizaron la multiplicación de matrices rápida para mejorar el algoritmo O ( m 3/2 ) para encontrar triángulos hasta 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 . [30]
Listado de todas las camarillas máximas
Según el resultado de Moon y Moser (1965) , cada gráfico de n -vértices tiene como máximo 3 n / 3 camarillas máximas. Pueden enumerarse mediante el algoritmo de Bron – Kerbosch , un procedimiento de retroceso recursivo de Bron y Kerbosch (1973) . La principal subrutina recursiva 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 volver a agregar. Se puede demostrar que las variantes de este algoritmo tienen un tiempo de ejecución en el peor de los casos O (3 n / 3 ) , coincidiendo con el número de camarillas que podrían necesitar ser enumeradas. [31] Por lo tanto, esto proporciona una solución óptima en el peor de los casos al problema de enumerar todas las camarillas máximas. Además, se ha informado ampliamente que el algoritmo de Bron-Kerbosch es más rápido en la práctica que sus alternativas. [32]
Sin embargo, cuando el número de camarillas es significativamente menor que en el peor de los casos, pueden ser preferibles otros algoritmos. Como Tsukiyama et al. (1977) demostró 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 de ellos 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, relacionando las camarillas máximas del gráfico G dado con las camarillas máximas de una gráfica G \ v formada 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 sí contiene v se puede formar a partir de una camarilla máxima K en G \ v sumando 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 , produce tanto K como la camarilla formada al sumar v a K y eliminar el no -vecinos del v . Sin embargo, algunas camarillas de G pueden generarse de esta manera a partir de más de una camarilla padre de G \ v , por lo que eliminan los duplicados generando una camarilla en G solo cuando su padre en G \ v es lexicográficamente máximo entre todas las camarillas padres posibles. Sobre la base de este principio, muestran que todas las camarillas máximas en G pueden generarse 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) muestran que incluso es posible enumerar todas las camarillas máximas en orden lexicográfico con retardo polinomial por camarilla. Sin embargo, la elección del orden es importante para la eficiencia de este algoritmo: para el inverso de este orden, no existe un algoritmo de retardo polinómico a menos que P = NP .
Sobre la base de este resultado, es posible enumerar todas las camarillas máximas en tiempo polinomial, para familias de gráficos en las que el número de camarillas está acotado polinomialmente. 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 . [33] En particular, los gráficos planos tienen O ( n ) camarillas, de tamaño constante como máximo, que se pueden enumerar en tiempo lineal. Lo mismo es cierto para cualquier familia de gráficos que sea escasa (que tenga un número de aristas como máximo una constante multiplicada por el número de vértices) y cerrada bajo la operación de tomar subgráficos. [19] [34]
Encontrar camarillas máximas en gráficos arbitrarios
Es posible encontrar la camarilla máxima, o el número de camarilla, de un gráfico arbitrario de n -vértices 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 de Bron – Kerbosch , pero es capaz de 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 se calcula previamente la solución óptima para todos los subgráficos pequeños conectados del gráfico del complemento . Estas soluciones parciales se utilizan para atajar la recursividad de retroceso. El algoritmo más rápido conocido en la actualidad 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 ) . [35]
También ha habido una extensa investigación sobre algoritmos heurísticos para resolver problemas de clique máximo sin garantías de tiempo de ejecución en el peor de los casos, basados en métodos que incluyen bifurcación y enlace , [36] búsqueda local , [37] algoritmos codiciosos , [38] y programación de restricciones . [39] Las metodologías de computación no estándar que se han sugerido para encontrar camarillas incluyen la computación de ADN [40] y la computación cuántica adiabática . [41] El problema de la camarilla máxima fue objeto de un desafío de implementación patrocinado por DIMACS en 1992-1993, [42] y una colección de gráficos utilizados como puntos de referencia para el desafío, que está disponible públicamente. [43]
Clases especiales de gráficos
Las gráficas planas y otras familias de gráficas dispersas se han discutido anteriormente: tienen linealmente muchas camarillas máximas, de tamaño acotado, que pueden enumerarse en tiempo lineal. [19] En particular, para los gráficos planos, cualquier camarilla puede tener como máximo cuatro vértices, según el teorema de Kuratowski . [22]
Los gráficos perfectos se definen por las propiedades de que su número de camarilla es igual a su número cromático , y que esta igualdad se mantiene también en cada uno de sus subgrafos inducidos . Para gráficos perfectos, es posible encontrar una camarilla máxima en tiempo polinomial, utilizando un algoritmo basado en programación semidefinida . [44] Sin embargo, este método es complejo y no combinatorio, y se han desarrollado algoritmos especializados de búsqueda de camarillas para muchas subclases de gráficos perfectos. [45] En los gráficos de complemento de grafos bipartitos , el teorema de König permite el problema máximo camarilla a ser resuelto usando técnicas de coincidencia . En otra clase de gráficos perfectos, los gráficos de permutación , una camarilla máxima es una subsecuencia decreciente más larga de la permutación que define el gráfico y se puede encontrar usando algoritmos conocidos para el problema de subsecuencia decreciente más larga. A la inversa, cada instancia del problema de subsecuencia decreciente más larga puede describirse de manera equivalente como un problema de encontrar una camarilla máxima en un gráfico de permutación. [46] Incluso, Pnueli y Lempel (1972) proporcionan un algoritmo alternativo de tiempo cuadrático para grupos máximos en gráficos de comparabilidad , una clase más amplia de gráficos perfectos que incluye los gráficos de permutación como un caso especial. [47] En los gráficos cordales , las camarillas máximas se pueden encontrar enumerando los vértices en un orden de eliminación y verificando las vecindades de las camarillas de cada vértice en este orden. [48]
En algunos casos, estos algoritmos también pueden extenderse a otras clases de gráficos no perfectos. Por ejemplo, en un gráfico circular , la vecindad de cada vértice es una gráfica de permutación, por lo que se puede encontrar una camarilla máxima en una gráfica circular aplicando el algoritmo de gráfica de permutación a cada vecindad. [49] De manera similar, en un gráfico de disco unitario (con una representación geométrica conocida), existe un algoritmo de tiempo polinomial para cliques máximos basado en la aplicación del algoritmo para complementos de gráficos bipartitos a vecindades compartidas de pares de vértices. [50]
El problema algorítmico de encontrar una camarilla máxima en un gráfico aleatorio extraído del modelo Erdős-Rényi (en el que cada borde aparece con probabilidad 1/2 , independientemente de los otros bordes) fue sugerido por Karp (1976) . Debido a que la camarilla máxima en un gráfico aleatorio tiene un tamaño logarítmico con alta probabilidad, se puede encontrar mediante una búsqueda de fuerza bruta en el tiempo esperado 2 O (log 2 n ) . Este es un límite de tiempo cuasi-polinomial . [51] Aunque el número de camarillas de tales gráficos suele ser muy cercano a 2 log 2 n , los algoritmos codiciosos simples, así como las técnicas de aproximación aleatorias más sofisticadas, solo encuentran camarillas con un tamaño log 2 n , la mitad de grande. El número de camarillas máximas en tales gráficos es con alta probabilidad exponencial en log 2 n , lo que evita que los métodos que enumeran todas las camarillas máximas se ejecuten en tiempo polinomial. [52] Debido a la dificultad de este problema, varios autores han investigado el problema de la camarilla plantada , el problema de la camarilla en gráficos aleatorios que se han aumentado mediante la adición de grandes camarillas. [53] Si bien los métodos espectrales [54] y la programación semidefinida [55] pueden detectar camarillas ocultas de tamaño Ω ( √ n ) , actualmente no se conocen algoritmos de tiempo polinomial que detecten aquellos de tamaño o ( √ n ) (expresados con poco o notación ). [56]
Algoritmos de aproximación
Varios autores han considerado algoritmos de aproximación que intentan encontrar una camarilla o conjunto independiente que, aunque no sea el máximo, tenga un tamaño tan cercano al máximo como se puede encontrar en el tiempo polinomial. Aunque gran parte de este trabajo se ha centrado en conjuntos independientes en gráficos dispersos, un caso que no tiene sentido para el problema de la camarilla complementaria, también se ha trabajado en algoritmos de aproximación que no utilizan tales supuestos de dispersión. [57]
Feige (2004) describe un algoritmo de tiempo polinomial que encuentra una camarilla de tamaño Ω ((log n / log log n ) 2 ) en cualquier gráfico que tenga un número de camarilla Ω ( n / log k n ) para cualquier constante k . Usando este algoritmo cuando el número de camarilla de un gráfico de entrada dado está entre n / log n y n / log 3 n , cambiando a un algoritmo diferente de Boppana y Halldórsson (1992) para gráficos con números de camarilla más altos, y eligiendo un dos- camarilla de vértices si ambos algoritmos no encuentran nada, Feige proporciona un algoritmo de aproximación que encuentra una camarilla con un número de vértices dentro de un factor de O ( n (log log n ) 2 / log 3 n ) del máximo. Aunque la relación de aproximación de este algoritmo es débil, es el más conocido hasta la fecha. [58] Los resultados sobre la dureza de aproximación que se describen a continuación sugieren que no puede haber un algoritmo de aproximación con una relación de aproximación significativamente menor que la lineal.
Límites inferiores
NP-completitud
El problema de la decisión de la camarilla es NP-completo . Fue uno de los 21 problemas originales de Richard Karp que se muestra NP-completo en su artículo de 1972 "Reducibilidad entre problemas combinatorios". [60] Este problema también se mencionó en el artículo de Stephen Cook que presenta la teoría de problemas NP-completos. [61] Debido a la dureza del problema de decisión, el problema de encontrar una camarilla máxima también es NP-difícil. Si uno pudiera resolverlo, también podría resolver el problema de decisión, comparando el tamaño de la camarilla máxima con el parámetro de tamaño dado como entrada en el problema de decisión.
La prueba de completitud NP de Karp es una reducción de muchos uno del problema de satisfacibilidad booleano . Describe cómo traducir fórmulas booleanas en forma conjuntiva normal (CNF) en instancias equivalentes del problema de la camarilla máxima. [62] La satisfacción, a su vez, se demostró NP-completa en el teorema de Cook-Levin . A partir de una fórmula CNF dada, Karp forma una gráfica que tiene un vértice para cada par ( v , c ) , donde v es una variable o su negación yc es una cláusula en la fórmula que contiene v . Dos de estos vértices están conectados por un borde si representan asignaciones de variables compatibles para diferentes cláusulas. Es decir, hay una arista de ( v , c ) a ( u , d ) siempre que c ≠ d y u y v no son negaciones de cada uno. Si k denota el número de cláusulas en la fórmula CNF, entonces las camarillas k -vertex en este gráfico representan formas consistentes de asignar valores de verdad a algunas de sus variables para satisfacer la fórmula. Por lo tanto, la fórmula es satisfactoria si y solo si existe una camarilla de k- vértices. [60]
Algunos problemas NP-completos (como el problema del viajante de comercio en gráficas planas ) pueden resolverse en un tiempo exponencial en una función sublineal del parámetro de tamaño de entrada n , significativamente más rápido que una búsqueda de fuerza bruta. [63] Sin embargo, es poco probable que tal límite de tiempo subexponencial sea posible para el problema de la camarilla en gráficos arbitrarios, ya que implicaría límites subexponenciales similares para muchos otros problemas estándar NP-completos. [64]
Complejidad del circuito
La dificultad computacional del problema de la camarilla ha llevado a que se utilice para probar varios límites inferiores en la complejidad del circuito . La existencia de una camarilla de un tamaño dado es una propiedad de gráfico monótona , lo que significa que, si existe una camarilla en un gráfico dado, existirá en cualquier supergrafía . Debido a esta propiedad es monótona, debe existir un circuito monótona, utilizando sólo y puertas y o puertas , para resolver el problema de decisión camarilla para un tamaño fijo dado camarilla. Sin embargo, se puede demostrar que el tamaño de estos circuitos es una función superpolinomial del número de vértices y el tamaño de la camarilla, exponencial en la raíz cúbica del número de vértices. [65] Incluso si se permite un pequeño número de puertas NOT , la complejidad sigue siendo superpolinomial. [66] Además, la profundidad de un circuito monótono para el problema de la camarilla que utiliza puertas de abanico limitado debe ser al menos un polinomio en el tamaño de la camarilla. [67]
Complejidad del árbol de decisiones
La complejidad del árbol de decisión (determinista) de determinar una propiedad de gráfico es el número de preguntas de la forma "¿Hay una arista entre el vértice u y el vértice v ?" que deben responderse en el peor de los casos para determinar si un gráfico tiene una propiedad particular. Es decir, es la altura mínima de un árbol de decisión booleano para el problema. Hay n ( n - 1) / 2 preguntas posibles. Por lo tanto, cualquier propiedad de la gráfica se puede determinar con un máximo de n ( n - 1) / 2 preguntas. También es posible definir la complejidad del árbol de decisión aleatorio y cuántico de una propiedad, el número esperado de preguntas (para la entrada del peor de los casos) que un algoritmo aleatorio o cuántico debe responder para determinar correctamente si el gráfico dado tiene la propiedad . [68]
Debido a que la propiedad de contener una camarilla es monótona, está cubierta por la conjetura de Aanderaa-Karp-Rosenberg , que establece que la complejidad del árbol de decisión determinista para determinar cualquier propiedad de grafo monótono no trivial es exactamente n ( n - 1) / 2 . Para las propiedades arbitrarias de un gráfico monótono, esta conjetura no se ha probado. Sin embargo, para los árboles de decisión deterministas, y para cualquier k en el rango de 2 ≤ k ≤ n , la propiedad de contener un k -clique ha demostrado tener la complejidad del árbol de decisión exactamente n ( n - 1) / 2 por Bollobás (1976) . Los árboles de decisión deterministas también requieren un tamaño exponencial para detectar camarillas, o un tamaño polinomial grande para detectar camarillas de tamaño limitado. [69]
La conjetura de Aanderaa-Karp-Rosenberg también establece que la complejidad del árbol de decisión aleatorio de las funciones monótonas no triviales es Θ ( n 2 ) . Nuevamente, la conjetura permanece sin probar, pero se ha resuelto por la propiedad de contener una camarilla k para 2 ≤ k ≤ n . Se sabe que esta propiedad tiene una complejidad de árbol de decisión aleatoria Θ ( n 2 ) . [70] Para los árboles de decisión cuántica, el límite inferior más conocido es Ω ( n ) , pero no se conoce ningún algoritmo de coincidencia para el caso de k ≥ 3 . [71]
Intratabilidad de parámetros fijos
La complejidad parametrizada es el estudio teórico de la complejidad de problemas que están naturalmente equipados con un parámetro de entero pequeño k y para los cuales el problema se vuelve más difícil a medida que k aumenta, como encontrar k -cliques en los gráficos. Se dice que un problema es tratable con parámetros fijos si hay un algoritmo para resolverlo en entradas de tamaño n , y una función f , de modo que el algoritmo se ejecute en el tiempo f ( k ) n O (1) . Es decir, es tratable con parámetros fijos si se puede resolver en tiempo polinomial para cualquier valor fijo de k y además si el exponente del polinomio no depende de k . [72]
Para encontrar camarillas de k- vértices, el algoritmo de búsqueda de fuerza bruta tiene un tiempo de ejecución O ( n k k 2 ) . Debido a que el exponente de n depende de k , este algoritmo no es manejable con parámetros fijos. Aunque se puede mejorar mediante la multiplicación rápida de matrices, el tiempo de ejecución todavía tiene un exponente que es lineal en k Por lo tanto, aunque el tiempo de ejecución de los algoritmos conocidos para el problema de la camarilla es polinomial para cualquier k fijo , estos algoritmos no son suficientes para parámetros fijos tractabilidad. Downey y Fellows (1995) definieron una jerarquía de problemas parametrizados, la jerarquía W, que conjeturaron que no tenían algoritmos manejables de parámetros fijos. Demostraron que el conjunto independiente (o, equivalentemente, camarilla) es difícil para el primer nivel de esta jerarquía, W [1] . Por lo tanto, de acuerdo con su conjetura, la camarilla no tiene un algoritmo manejable de parámetros fijos. Además, este resultado proporciona la base para las pruebas de dureza W [1] de muchos otros problemas y, por lo tanto, sirve como análogo del teorema de Cook-Levin para la complejidad parametrizada. [73]
Chen y col. (2006) demostraron que no es posible encontrar camarillas de k- vértices en el tiempo n o ( k ) a menos que falle la hipótesis del tiempo exponencial . Nuevamente, esto proporciona evidencia de que no es posible ningún algoritmo manejable de parámetros fijos. [74]
Aunque es poco probable que los problemas de enumerar las camarillas máximas o encontrar las camarillas máximas sean tratables con parámetros fijos con el parámetro k , pueden ser tratables con parámetros fijos para otros parámetros de complejidad de instancia. Por ejemplo, se sabe que ambos problemas se pueden tratar con parámetros fijos cuando se parametrizan por la degeneración del gráfico de entrada. [34]
Dureza de aproximación
Los resultados débiles que insinúan que el problema de la camarilla podría ser difícil de aproximar se conocen desde hace mucho tiempo. Garey y Johnson (1978) observaron que, debido al hecho de que el número de clique toma valores enteros pequeños y es NP-difícil de calcular, no puede tener un esquema de aproximación de tiempo polinomial completo . Si se dispusiera de una aproximación demasiado precisa, redondear su valor a un número entero daría el número de camarilla exacto. Sin embargo, poco más se supo hasta principios de la década de 1990, cuando varios autores comenzaron a establecer conexiones entre la aproximación de las camarillas máximas y las pruebas probabilísticamente verificables . Utilizaron estas conexiones para probar la dureza de los resultados de aproximación para el problema de la camarilla máxima. [75] Después de muchas mejoras en estos resultados, ahora se sabe que, para cada número real ε > 0 , no puede haber un algoritmo de tiempo polinomial que se aproxime a la camarilla máxima dentro de un factor mejor que O ( n 1 - ε ) , a menos que P = NP . [76]
La idea aproximada de estos resultados de inaproximabilidad es formar un gráfico que represente un sistema de prueba probabilísticamente verificable para un problema NP completo, como el problema de satisfacibilidad booleano. En un sistema de prueba comprobable probabilísticamente, una prueba se representa como una secuencia de bits. Una instancia del problema de satisfacibilidad debe tener una prueba válida si y solo si es satisfactoria. La prueba es verificada por un algoritmo que, después de un cálculo de tiempo polinomial en la entrada al problema de satisfacibilidad, elige examinar un pequeño número de posiciones elegidas al azar de la cadena de prueba. Dependiendo de los valores que se encuentren en esa muestra de bits, el verificador aceptará o rechazará la prueba, sin mirar el resto de los bits. No se permiten falsos negativos: siempre se debe aceptar una prueba válida. Sin embargo, a veces se puede aceptar por error una prueba no válida. Para cada prueba inválida, la probabilidad de que el verificador la acepte debe ser baja. [77]
Para transformar un sistema de prueba probabilísticamente comprobable de este tipo en un problema de camarilla, se forma un gráfico con un vértice para cada posible ejecución de aceptación del corrector de pruebas. Es decir, un vértice se define por una de las posibles elecciones aleatorias de conjuntos de posiciones a examinar y por valores de bits para aquellas posiciones que harían que el verificador aceptara la prueba. Puede estar representado por una palabra parcial con un 0 o 1 en cada posición examinada y un carácter comodín en cada posición restante. Dos vértices son adyacentes, en este gráfico, si las dos corridas de aceptación correspondientes ven los mismos valores de bit en cada posición que ambos examinan. Cada cadena de prueba (válida o no válida) corresponde a una camarilla, el conjunto de corridas de aceptación que ven esa cadena de prueba, y todas las camarillas máximas surgen de esta manera. Una de estas camarillas es grande si y solo si corresponde a una cadena de prueba que muchos verificadores aceptan. Si la instancia de satisfacibilidad original es satisfactoria, tendrá una cadena de prueba válida, una que sea aceptada por todas las ejecuciones del verificador, y esta cadena corresponderá a una pandilla grande en el gráfico. Sin embargo, si la instancia original no es satisfactoria, entonces todas las cadenas de prueba no son válidas, cada cadena de prueba tiene solo una pequeña cantidad de corridas de verificación que la aceptan por error y todas las camarillas son pequeñas. Por lo tanto, si uno pudiera distinguir en el tiempo polinómico entre gráficos que tienen grupos grandes y gráficos en los que todos los grupos son pequeños, o si uno pudiera aproximar con precisión el problema de los grupos, entonces aplicar esta aproximación a los gráficos generados a partir de instancias de satisfacibilidad permitiría que las instancias satisfactorias distinguirse de los casos insatisfactorios. Sin embargo, esto no es posible a menos que P = NP. [77]
Notas
- ^ a b c Bomze y col. (1999) ; Gutin (2004) .
- ^ Wasserman y Faust (1994) .
- ^ Kolata (1990) .
- ^ Rhodes y col. (2003) .
- ^ Kuhl, Crippen y Friesen (1983) .
- ^ Comité del Consejo Nacional de Investigación sobre Desafíos Matemáticos de la Química Computacional (1995) . Véanse en particular las págs. 35–36 .
- ^ Muegge y Rarey (2001) . Véanse en particular las págs. 6–7 .
- ^ Barrow y Burstall (1976) .
- ^ Hamzaoglu y Patel (1998) .
- ^ Day y Sankoff (1986) .
- ^ Samudrala y Moult (1998) .
- ^ Spirin y Mirny (2003) .
- ^ Frank y Strauss (1986) .
- ^ El gráfico de Keller utilizado por Lagarias y Shor (1992) tiene 1048576 vértices y un tamaño de camarilla 1024. Describieron una construcción sintética para la camarilla, pero también utilizaron algoritmos de búsqueda de camarillas en gráficos más pequeños para ayudar a guiar su búsqueda. Mackey (2002) simplificó la demostración al encontrar una camarilla de tamaño 256 en un gráfico de Keller de 65536 vértices.
- ↑ a b Valiente (2002) ; Pelillo (2009) .
- ^ Pelillo (2009) .
- ^ Sethuraman y Butenko (2015) .
- ^ Valiente (2002) .
- ↑ a b c d Chiba y Nishizeki (1985) .
- ^ a b Cormen y col. (2001) .
- ^ Cormen y col. (2001) , ejercicio 34-1, p. 1018.
- ↑ a b Papadimitriou y Yannakakis (1981) ; Chiba y Nishizeki (1985) .
- ^ Garey, Johnson y Stockmeyer (1976) .
- ^ Véase, por ejemplo, Frank y Strauss (1986) .
- ^ Plummer (1993) .
- ^ Skiena (2009) , p. 526 .
- ^ Cook (1985) .
- ^ Por ejemplo, véase Downey & Fellows (1995) .
- ^ Itai y Rodeh (1978) proporcionan un algoritmo contiempo de ejecución O ( m 3/2 ) que encuentra un triángulo, si existe, pero no enumera todos los triángulos; Chiba y Nishizeki (1985) enumeran todos los triángulos en el tiempo O ( m 3/2 ) .
- ^ Eisenbrand y Grandoni (2004) ; Kloks, Kratsch y Müller (2000) ; Nešetřil y Poljak (1985) ; Vassilevska y Williams (2009) ; Yuster (2006) .
- ^ Tomita, Tanaka y Takahashi (2006) .
- ^ Cazals y Karande (2008) ; Eppstein, Löffler y Strash (2013) .
- ^ Rosgen y Stewart (2007) .
- ↑ a b Eppstein, Löffler y Strash (2013) .
- ^ Robson (2001) .
- ^ Balas y Yu (1986) ; Carraghan y Pardalos (1990) ; Pardalos y Rogers (1992) ; Östergård (2002) ; Fahle (2002) ; Tomita y Seki (2003) ; Tomita y Kameda (2007) ; Konc y Janežič (2007) .
- ^ Battiti y Protasi (2001) ; Katayama, Hamamoto y Narihisa (2005) .
- ^ Abello, Pardalos y Resende (1999) ; Grosso, Locatelli y Della Croce (2004) .
- ^ Régin (2003) .
- ^ Ouyang y col. (1997) . Aunque el título se refiere a las camarillas máximas, el problema que resuelve este artículo es en realidad el problema de las camarillas máximas.
- ^ Childs y col. (2002) .
- ^ Johnson y Trick (1996) .
- ^ Gráficos de desafío DIMACS para el problema de la camarilla Archivado el 30 de marzo de 2018 en Wayback Machine , consultado el17 de diciembre de 2009.
- ^ Grötschel, Lovász y Schrijver (1988) .
- ^ Golumbic (1980) .
- ^ Golumbic (1980) , p. 159.
- ^ Incluso, Pnueli y Lempel (1972) .
- ^ Blair y Peyton (1993) , Lema 4.5, p. 19.
- ^ Gavril (1973) ; Golumbic (1980) , pág. 247.
- ^ Clark, Colbourn y Johnson (1990) .
- ^ Canción (2015) .
- ^ Jerrum (1992) .
- ^ Arora y Barak (2009) , ejemplo 18.2, págs. 362–363.
- ^ Alon, Krivelevich y Sudakov (1998) .
- ^ Feige y Krauthgamer (2000) .
- ^ Meka, Potechin y Wigderson (2015) .
- ^ Boppana y Halldórsson (1992) ; Feige (2004) ; Halldórsson (2000) .
- ^ Liu y col. (2015) : "En términos del número de vértices en los gráficos, Feige muestra la mejor relación de aproximación conocida actualmente". Liu y col. escriben sobre el conjunto máximo independiente, pero para fines de aproximación no hay diferencia entre los dos problemas.
- ^ Adaptado de Sipser (1996)
- ↑ a b Karp (1972) .
- ^ Cook (1971) .
- ↑ Cook (1971) ofrece esencialmente la misma reducción, de 3-SAT en lugar de Satisfiability, para mostrar que el isomorfismo del subgrafo es NP-completo.
- ^ Lipton y Tarjan (1980) .
- ^ Impagliazzo, Paturi y Zane (2001) .
- ^ Alon y Boppana (1987) . Para límites más tempranos y débiles en circuitos monótonos para el problema de la camarilla, ver Valiant (1983) y Razborov (1985) .
- ^ Amano y Maruoka (2005) .
- ↑ Goldmann y Håstad (1992) utilizaron la complejidad de la comunicación para demostrar este resultado.
- ^ Véase Arora y Barak (2009) , Capítulo 12, "Árboles de decisión", págs. 259-269.
- ^ Wegener (1988) .
- ^ Por ejemplo, esto se sigue de Gröger (1992) .
- ^ Childs y Eisenberg (2005) ; Magniez, Santha y Szegedy (2007) .
- ^ Downey y becarios (1999) . Técnicamente, suele existir un requisito adicional de que f sea una función computable .
- ^ Downey y becarios (1995) .
- ^ Chen y col. (2006) .
- ^ Kolata (1990) ; Feige y col. (1991) ; Arora y Safra (1998) ; Arora y col. (1998) .
- ^ Håstad (1999) mostró inapropiabilidad para esta relación utilizando un supuesto teórico de complejidad más fuerte, la desigualdad de NP y ZPP . Khot (2001) describió con más precisión la razón de inaproximabilidad, pero con un supuesto aún más fuerte. Zuckerman (2006) desaleatorizó la construcción debilitando su supuesto a P ≠ NP.
- ^ a b Esta reducción se debe originalmente a Feige et al. (1991) y se utiliza en todas las pruebas de inapropiabilidad posteriores; las pruebas difieren en las fortalezas y detalles de los sistemas de prueba probabilísticamente verificables en los que se basan.
Referencias
Encuestas y libros de texto
- Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, ISBN 978-0-521-42426-4.
- Blair, Jean RS; Peyton, Barry (1993), "Una introducción a los gráficos cordales y los árboles clique", Teoría de grafos y cálculo de matrices dispersas , IMA Vol. Matemáticas. Appl., 56 , Springer, Nueva York, págs. 1–29, doi : 10.1007 / 978-1-4613-8369-7_1 , MR 1320296.
- Bomze, MI; Budinich, M .; Pardalos, PM; Pelillo, M. (1999), "El problema de la camarilla máxima", Manual de optimización combinatoria , 4 , Kluwer Academic Publishers, págs. 1-74, CiteSeerX 10.1.1.48.4074.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "34.5.1 El problema de la camarilla", Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill, págs. 1003–1006, ISBN 0-262-03293-7.
- Downey, RG; Becarios, MR (1999), Complejidad parametrizada , Springer-Verlag , ISBN 0-387-94883-X.
- Golumbic, MC (1980), Teoría algorítmica de grafos y gráficos perfectos , Informática y matemáticas aplicadas, Academic Press , ISBN 0-444-51530-5.
- Grötschel, M .; Lovász, L .; Schrijver, A. (1988), "9.4 Colorear gráficos perfectos", algoritmos geométricos y optimización combinatoria , algoritmos y combinatoria, 2 , Springer-Verlag , págs. 296-298, ISBN 0-387-13624-X.
- Gutin, G. (2004), "5.3 Grupos y camarillas independientes", en Gross, JL; Yellen, J. (eds.), Manual de teoría de grafos , Matemáticas discretas y sus aplicaciones, CRC Press, págs. 389–402, ISBN 978-1-58488-090-5.
- Muegge, Ingo; Rarey, Matthias (2001), "Acoplamiento y puntuación de moléculas pequeñas", Reviews in Computational Chemistry , 17 : 1–60, doi : 10.1002 / 0471224413.ch1 , ISBN 9780471398455.
- Comité del Consejo Nacional de Investigación sobre Desafíos Matemáticos de la Química Computacional (1995), Desafíos Matemáticos de la Química Teórica / Computacional , National Academies Press, doi : 10.17226 / 4886 , ISBN 978-0-309-05097-5.
- Pelillo, Marcello (2009), "Heurísticas para un grupo máximo y un conjunto independiente", Enciclopedia de optimización , Springer, págs. 1508-1520, doi : 10.1007 / 978-0-387-74759-0_264.
- Plummer, Michael D. (1993), "Gráficos bien cubiertos: una encuesta" , Quaestiones Mathematicae , 16 (3): 253–287, doi : 10.1080 / 16073606.1993.9631737 , MR 1254158.
- Sipser, M. (1996), Introducción a la teoría de la computación , International Thompson Publishing , ISBN 0-534-94728-X.
- Skiena, Steven S. (2009), Manual de diseño de algoritmos (2a ed.), Springer, ISBN 978-1-84800-070-4.
- Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algoritmos sobre árboles y gráficos , Springer, págs. 299-350, doi : 10.1007 / 978-3-662-04921-1_6.
- Wasserman, Stanley ; Faust, Katherine (1994), Social Network Analysis: Methods and Applications , Structural Analysis in the Social Sciences, 8 , Cambridge University Press, p. 276, ISBN 978-0-521-38707-1.
Prensa popular
- Kolata, Gina (26 de junio de 1990), "En un frenesí, las matemáticas entran en la era del correo electrónico" , The New York Times.
Artículos de investigación
- Abello, J .; Pardalos, PM; Resende, MGC (1999), "Sobre problemas de pandillas máximas en gráficos muy grandes" (PDF) , en Abello, J .; Vitter, J. (eds.), Algoritmos de memoria externa , Serie DIMACS sobre matemáticas discretas e informática teórica, 50 , American Mathematical Society , págs. 119-130, ISBN 0-8218-1184-3.
- Alon, N .; Boppana, R. (1987), "La complejidad del circuito monótono de las funciones booleanas", Combinatorica , 7 (1): 1–22, doi : 10.1007 / BF02579196 , S2CID 17397273.
- Alon, N .; Krivelevich, M .; Sudakov, B. (1998), "Encontrar una gran camarilla oculta en un gráfico aleatorio", Estructuras y algoritmos aleatorios , 13 (3–4): 457–466, doi : 10.1002 / (SICI) 1098-2418 (199810/12 ) 13: 3/4 <457 :: AID-RSA14> 3.0.CO; 2-W.
- Alon, N .; Yuster, R .; Zwick, U. (1994), "Encontrar y contar ciclos de longitud dados", Actas del 2º Simposio Europeo de Algoritmos, Utrecht, Países Bajos , págs. 354–364.
- Amano, Kazuyuki; Maruoka, Akira (2005), "Un límite inferior superpolinomial para un circuito que calcula la función clique con un máximo de (1/6) puertas de negación log log N ", SIAM Journal on Computing , 35 (1): 201-216, doi : 10.1137 / S0097539701396959 , MR 2178806.
- Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudán, Madhu ; Szegedy, Mario (1998), "Verificación de la prueba y la dureza de los problemas de aproximación", Journal of the ACM , 45 (3): 501–555, doi : 10.1145 / 278298.278306 , S2CID 8561542 , ECCC TR98-008. Presentado originalmente en el Simposio de 1992 sobre los fundamentos de la informática , doi : 10.1109 / SFCS.1992.267823 .
- Arora, S .; Safra, S. (1998), "Comprobación probabilística de pruebas: una nueva caracterización de NP", Journal of the ACM , 45 (1): 70-122, doi : 10.1145 / 273865.273901 , S2CID 751563. Presentado originalmente en el Simposio de 1992 sobre los fundamentos de la informática , doi : 10.1109 / SFCS.1992.267824 .
- Balas, E .; Yu, CS (1986), "Encontrar una camarilla máxima en un gráfico arbitrario", SIAM Journal on Computing , 15 (4): 1054–1068, doi : 10.1137 / 0215075.
- Barrow, H .; Burstall, R. (1976), "Isomorfismo de subgrafo, emparejamiento de estructuras relacionales y camarillas máximas", Information Processing Letters , 4 (4): 83–84, doi : 10.1016 / 0020-0190 (76) 90049-1.
- Battiti, R .; Protasi, M. (2001), "Búsqueda local reactiva para el problema de la camarilla máxima", Algorithmica , 29 (4): 610–637, doi : 10.1007 / s004530010074 , S2CID 1800512.
- Bollobás, Béla (1976), "Los subgrafos completos son esquivos", Journal of Combinatorial Theory , Serie B, 21 (1): 1-7, doi : 10.1016 / 0095-8956 (76) 90021-6 , ISSN 0095-8956.
- Boppana, R .; Halldórsson, MM (1992), "Aproximación de conjuntos independientes máximos excluyendo subgráficos", BIT Numerical Mathematics , 32 (2): 180-196, doi : 10.1007 / BF01994876 , S2CID 123335474.
- Bron, C .; Kerbosch, J. (1973), "Algoritmo 457: encontrar todas las camarillas de un gráfico no dirigido", Comunicaciones del ACM , 16 (9): 575–577, doi : 10.1145 / 362342.362367 , S2CID 13886709.
- Carraghan, R .; Pardalos, PM (1990), "Un algoritmo exacto para el problema de la camarilla máxima", Cartas de investigación de operaciones , 9 (6): 375–382, doi : 10.1016 / 0167-6377 (90) 90057-C.
- Cazals, F .; Karande, C. (2008), "Una nota sobre el problema de informar sobre las camarillas máximas", Informática teórica , 407 (1): 564–568, doi : 10.1016 / j.tcs.2008.05.010.
- Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A .; Xia, Ge (2006), "Límites inferiores computacionales fuertes a través de la complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346-1367, doi : 10.1016 / j.jcss.2006.04.007
- Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph Listing Algoritmos", SIAM Journal on Computing , 14 (1): 210-223, doi : 10.1137 / 0214017.
- Childs, AM; Farhi, E .; Goldstone, J .; Gutmann, S. (2002), "Encontrar camarillas por evolución adiabática cuántica", Computación e información cuántica , 2 (3): 181-191, arXiv : quant-ph / 0012104 , Bibcode : 2000quant.ph.12104C , doi : 10.26421 /QIC2.3 , S2CID 33643794.
- Childs, AM; Eisenberg, JM (2005), "Algoritmos cuánticos para la búsqueda de subconjuntos", Computación e información cuántica , 5 (7): 593–604, arXiv : quant-ph / 0311038 , Bibcode : 2003quant.ph.11038C , doi : 10.26421 / QIC5 .7 , S2CID 37556989.
- Clark, Brent N .; Colbourn, Charles J .; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics , 86 (1-3): 165-177, doi : 10.1016 / 0012-365X (90) 90358-O
- Cook, SA (1971), "La complejidad de los procedimientos de demostración de teoremas" , Proc. 3er Simposio ACM sobre Teoría de la Computación , págs. 151-158, doi : 10.1145 / 800157.805047 , S2CID 7573663.
- Cook, Stephen A. (1985), "Una taxonomía de problemas con algoritmos paralelos rápidos", Información y control , 64 (1-3): 2-22, doi : 10.1016 / S0019-9958 (85) 80041-3 , MR 0837088.
- Día, William HE; Sankoff, David (1986), "Complejidad computacional de inferir filogenias por compatibilidad", Zoología sistemática , 35 (2): 224-229, doi : 10.2307 / 2413432 , JSTOR 2413432.
- Downey, RG; Fellows, MR (1995), "Tratabilidad y completitud de parámetros fijos. II. Sobre la completitud para W [1]", Theoretical Computer Science , 141 (1-2): 109-131, doi : 10.1016 / 0304-3975 (94 ) 00097-3.
- Eisenbrand, F .; Grandoni, F. (2004), "Sobre la complejidad de la camarilla de parámetros fijos y el conjunto dominante", Informática teórica , 326 (1-3): 57-67, doi : 10.1016 / j.tcs.2004.05.009.
- Eppstein, David ; Löffler, Maarten; Strash, Darren (2013), "Listado de todas las camarillas máximas en grandes gráficos dispersos del mundo real en un tiempo casi óptimo", Journal of Experimental Algorithmics , 18 (3): 3.1, arXiv : 1103.0318 , doi : 10.1145 / 2543629 , S2CID 47515491.
- Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría" (PDF) , Compositio Mathematica , 2 : 463–470.
- Incluso, S .; Pnueli, A .; Lempel, A. (1972), "Gráficos de permutación y gráficos transitivos", Journal of the ACM , 19 (3): 400–410, doi : 10.1145 / 321707.321710 , S2CID 9501737.
- Fahle, T. (2002), "Simple y rápido: Mejora de un algoritmo de bifurcación y enlace para una camarilla máxima", Proc. Décimo Simposio Europeo sobre Algoritmos , Lecture Notes in Computer Science, 2461 , Springer-Verlag, págs. 47–86, doi : 10.1007 / 3-540-45749-6_44 , ISBN 978-3-540-44180-9.
- Feige, U. (2004), "Aproximación de la camarilla máxima eliminando subgrafos", SIAM Journal on Discrete Mathematics , 18 (2): 219-225, doi : 10.1137 / S089548010240415X.
- Feige, U .; Goldwasser, S .; Lovász, L .; Safra, S ; Szegedy, M. (1991), "Aproximación a la camarilla es casi NP-completo", Proc. 32º IEEE Symp. on Foundations of Computer Science , págs. 2–12, doi : 10.1109 / SFCS.1991.185341 , ISBN 0-8186-2445-0, S2CID 46605913.
- 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.
- Frank, Ove; Strauss, David (1986), "Gráficos de Markov", Journal of the American Statistical Association , 81 (395): 832–842, doi : 10.2307 / 2289017 , JSTOR 2289017 , MR 0860518.
- Garey, MR ; Johnson, DS (1978), " " fuertes "Resultados de la NP-completitud: motivación, ejemplos y consecuencias", Revista de la ACM , 25 (3): 499-508, doi : 10.1145 / 322,077.322090 , S2CID 18371269.
- Garey, MR ; Johnson, DS ; Stockmeyer, L. (1976), "Algunos problemas de gráficos NP-completos simplificados", Informática teórica , 1 (3): 237-267, doi : 10.1016 / 0304-3975 (76) 90059-1 , MR 0411240.
- Gavril, F. (1973), "Algoritmos para una camarilla máxima y un conjunto máximo independiente de un gráfico circular", Redes , 3 (3): 261-273, doi : 10.1002 / net.3230030305.
- Goldmann, M .; Håstad, J. (1992), "Un límite inferior simple para una camarilla monótona usando un juego de comunicación" (PDF) , Information Processing Letters , 41 (4): 221-226, CiteSeerX 10.1.1.185.3065 , doi : 10.1016 / 0020 -0190 (92) 90184-W.
- Gröger, Hans Dietmar (1992), "Sobre la complejidad aleatorio de propiedades de gráfico monotono" (PDF) , Acta Cybernetica , 10 (3): 119-127 , recuperada 2009-10-02
- Grosso, A .; Locatelli, M .; Della Croce, F. (2004), "Combinación de intercambios y pesos de nodo en un enfoque codicioso adaptativo para el problema de la camarilla máxima", Journal of Heuristics , 10 (2): 135-152, doi : 10.1023 / B: HEUR.0000026264.51747. 7f , S2CID 40764225.
- Halldórsson, MM (2000), "Aproximaciones de problemas de conjuntos independientes ponderados y subconjuntos hereditarios", Journal of Graph Algorithms and Applications , 4 (1): 1-16, doi : 10.7155 / jgaa.00020.
- Hamzaoglu, I .; Patel, JH (1998), "Algoritmos de compactación de conjuntos de pruebas para circuitos combinacionales", Proc. 1998 IEEE / ACM International Conference on Computer-Aided Design , págs. 283–289, doi : 10.1145 / 288548.288615 , S2CID 12258606.
- Harary, F .; Ross, IC (1957), "Un procedimiento para la detección de camarillas usando la matriz de grupo", Sociometry , American Sociological Association, 20 (3): 205-215, doi : 10.2307 / 2785673 , JSTOR 2785673 , MR 0110590.
- Håstad, J. (1999), "La camarilla es difícil de aproximar dentro de n 1 - ε ", Acta Mathematica , 182 (1): 105-142, doi : 10.1007 / BF02392825.
- Impagliazzo, R .; Paturi, R .; Zane, F. (2001), "¿Qué problemas tienen una complejidad fuertemente exponencial?", Journal of Computer and System Sciences , 63 (4): 512-530, doi : 10.1006 / jcss.2001.1774.
- Itai, A .; Rodeh, M. (1978), "Encontrar un circuito mínimo en un gráfico", SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137 / 0207033.
- Jerrum, M. (1992), "Las grandes camarillas eluden el proceso de Metropolis", Estructuras y algoritmos aleatorios , 3 (4): 347–359, doi : 10.1002 / rsa.3240030402.
- Jian, T (1986), "Un algoritmo O (2 0.304 n ) para resolver un problema de conjunto independiente máximo", IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847–851, doi : 10.1109 / TC.1986.1676847 , ISSN 0018-9340.
- Johnson, DS ; Trick, MA , eds. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11-13 de octubre de 1993 , Serie DIMACS en Matemáticas Discretas y Ciencias de la Computación Teórica, 26 , American Mathematical Society , ISBN 0-8218-6609-5.
- Johnson, DS ; Yannakakis, M. (1988), "Sobre la generación de todos los conjuntos independientes máximos", Information Processing Letters , 27 (3): 119-123, doi : 10.1016 / 0020-0190 (88) 90065-8.
- Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", en Miller, RE; Thatcher, JW (eds.), Complexity of Computer Computations (PDF) , Nueva York: Plenum , págs. 85-103.
- Karp, Richard M. (1976), "Análisis probabilístico de algunos problemas de búsqueda combinatoria", en Traub, JF (ed.), Algorithms and Complexity: New Directions and Recent Results , Nueva York: Academic Press , págs. 1-19.
- Katayama, K .; Hamamoto, A .; Narihisa, H. (2005), "Una búsqueda local eficaz para el problema de la camarilla máxima", Information Processing Letters , 95 (5): 503–511, doi : 10.1016 / j.ipl.2005.05.010.
- Khot, S. (2001), "Resultados de inaproximabilidad mejorados para MaxClique, número cromático y coloración aproximada del gráfico", Proc. 42a IEEE Symp. Fundamentos de la informática , págs. 600–609, doi : 10.1109 / SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID 11987483.
- Kloks, T .; Kratsch, D .; Müller, H. (2000), "Encontrar y contar pequeños subgrafos inducidos de manera eficiente", Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016 / S0020-0190 (00) 00047-8.
- Konc, J .; Janežič, D. (2007), "Un algoritmo mejorado de rama y límite para el problema de la camarilla máxima" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (3): 569–590. Código fuente
- Kuhl, FS; Crippen, GM; Friesen, DK (1983), "Un algoritmo combinatorio para calcular la unión de ligandos", Journal of Computational Chemistry , 5 (1): 24–34, doi : 10.1002 / jcc.540050105.
- Lagarias, Jeffrey C .; Shor, Peter W. (1992), "La conjetura del mosaico de cubos de Keller es falsa en dimensiones elevadas", Boletín de la American Mathematical Society , New Series, 27 (2): 279-283, arXiv : math / 9210222 , doi : 10.1090 / S0273-0979-1992-00318-X , MR 1.155.280 , S2CID 6390600.
- Lipton, RJ ; Tarjan, RE (1980), "Aplicaciones de un teorema del separador plano", SIAM Journal on Computing , 9 (3): 615–627, doi : 10.1137 / 0209046 , S2CID 12961628.
- Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Hacia conjuntos máximos independientes en gráficos masivos", Actas de la 41ª Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB 2015) , Actas del VLDB Endowment, 8 , págs. 2122-2133, doi : 10.14778 /2831360.2831366 , hdl : 10138/157292.
- Luce, R. Duncan ; Perry, Albert D. (1949), "Un método de análisis matricial de la estructura del grupo", Psychometrika , 14 (2): 95-116, doi : 10.1007 / BF02289146 , hdl : 10.1007 / BF02289146 , PMID 18152948 , S2CID 16186758.
- Mackey, John (2002), "Un mosaico de cubos de dimensión ocho sin caras compartidas", Geometría discreta y computacional , 28 (2): 275-279, doi : 10.1007 / s00454-002-2801-9 , MR 1920144.
- Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), "Algoritmos cuánticos para el problema del triángulo", SIAM Journal on Computing , 37 (2): 413–424, arXiv : quant-ph / 0310134 , doi : 10.1137 / 050643684 , S2CID 594494.
- Makino, K .; Uno, T. (2004), "Nuevos algoritmos para enumerar todas las camarillas máximas", Teoría de algoritmos: SWAT 2004 (PDF) , Lecture Notes in Computer Science, 3111 , Springer-Verlag , pp. 260-272, CiteSeerX 10.1.1.138. 705 , doi : 10.1007 / 978-3-540-27810-8_23.
- Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares lower limits for plantged clique", Actas de la cuadragésima séptima reunión anual del ACM sobre el Simposio sobre Teoría de la Computación (STOC '15) , Nueva York, NY, EE. UU.: ACM, págs. . 87–96, arXiv : 1503.06447 , doi : 10.1145 / 2746539.2746600 , ISBN 978-1-4503-3536-2, S2CID 2754095.
- Luna, JW; Moser, L. (1965), "Sobre camarillas en gráficos", Israel Journal of Mathematics , 3 : 23-28, doi : 10.1007 / BF02760024 , MR 0182577 , S2CID 9855414.
- Nešetřil, J .; Poljak, S. (1985), "Sobre la complejidad del problema del subgrafo", Commentationes Mathematicae Universitatis Carolinae , 26 (2): 415–419.
- Östergård, PRJ (2002), "Un algoritmo rápido para el problema de la camarilla máxima", Matemáticas aplicadas discretas , 120 (1-3): 197-207, doi : 10.1016 / S0166-218X (01) 00290-6.
- Ouyang, Q .; Kaplan, PD; Liu, S .; Libchaber, A. (1997), "Solución de ADN del problema de la camarilla máxima", Science , 278 (5337): 446–449, Bibcode : 1997Sci ... 278..446O , doi : 10.1126 / science.278.5337.446 , PMID 9334300.
- Papadimitriou, Christos H .; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters , 13 (4-5): 131-133, doi : 10.1016 / 0020-0190 (81) 90041-7 , MR 0651460.
- Pardalos, PM; Rogers, GP (1992), "Un algoritmo de rama y límite para el problema de la camarilla máxima", Computers & Operations Research , 19 (5): 363–375, doi : 10.1016 / 0305-0548 (92) 90067-F.
- Razborov, AA (1985), "Límites inferiores para la complejidad monótona de algunas funciones booleanas", Actas de la Academia de Ciencias de la URSS (en ruso), 281 : 798–801. Traducción inglesa en Sov. Matemáticas. Dokl. 31 (1985): 354–357CS1 maint: posdata ( enlace ).
- Régin, J.-C. (2003), "Uso de la programación de restricciones para resolver el problema de la camarilla máxima", Proc. 9º Int. Conf. Principios y práctica de la programación de restricciones - CP 2003 , Lecture Notes in Computer Science, 2833 , Springer-Verlag , págs. 634–648, doi : 10.1007 / 978-3-540-45193-8_43.
- Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B .; Humblet, Christine (2003), "CLIP: búsqueda de similitudes de bases de datos 3D mediante detección de camarillas", Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi : 10.1021 / ci025605o , PMID 12653507.
- Robson, JM (1986), "Algoritmos para conjuntos máximos independientes", Journal of Algorithms , 7 (3): 425–440, doi : 10.1016 / 0196-6774 (86) 90032-5.
- Robson, JM (2001), Encontrar un conjunto independiente máximo en el tiempo O (2 n / 4 ).
- Rosgen, B; Stewart, L (2007), "Resultados de complejidad en gráficos con pocas camarillas" , Matemáticas discretas e informática teórica , 9 (1): 127-136.
- Samudrala, Ram; Moult, John (1998), "Un algoritmo teórico de gráficos para el modelado comparativo de la estructura de las proteínas", Journal of Molecular Biology , 279 (1): 287–302, doi : 10.1006 / jmbi.1998.1689 , PMID 9636717.
- Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science , 12 (1): 197–218, doi : 10.1007 / s10287-013-0197-z , MR 3296231 , S2CID 46153055.
- Song, Y. (2015), "Sobre el problema de conjuntos independientes en gráficas aleatorias" , International Journal of Computer Mathematics , 92 (11): 2233–2242, doi : 10.1080 / 00207160.2014.976210 , S2CID 6713201.
- Spirin, Victor; Mirny, Leonid A. (2003), "Complejos de proteínas y módulos funcionales en redes moleculares", Actas de la Academia Nacional de Ciencias , 100 (21): 12123-12128, Bibcode : 2003PNAS..10012123S , doi : 10.1073 / pnas. 2032324100 , PMC 218723 , PMID 14517352.
- Tarjan, RE ; Trojanowski, AE (1977), "Encontrar un conjunto máximo independiente" (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi : 10.1137 / 0206038.
- Tomita, E .; Kameda, T. (2007), "Un algoritmo eficiente de ramificación y enlace para encontrar una camarilla máxima con experimentos computacionales", Journal of Global Optimization , 37 (1): 95-111, doi : 10.1007 / s10898-006-9039 -7 , S2CID 21436014.
- Tomita, E .; Seki, T. (2003), "Un algoritmo eficiente de bifurcaciones y límites para encontrar una camarilla máxima" , Matemáticas discretas y Ciencias de la computación teóricas , Lecture Notes in Computer Science, 2731 , Springer-Verlag, pp. 278-289 , doi : 10.1007 / 3-540-45066-1_22 , ISBN 978-3-540-40505-4.
- Tomita, E .; Tanaka, A .; Takahashi, H. (2006), "La complejidad de tiempo en el peor de los casos para generar todas las camarillas máximas y experimentos computacionales", Informática teórica , 363 (1): 28–42, doi : 10.1016 / j.tcs.2006.06.015.
- Tsukiyama, S .; Ide, M .; Ariyoshi, I .; Shirakawa, I. (1977), "Un nuevo algoritmo para generar todos los conjuntos independientes máximos", SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137 / 0206036.
- Valiant, LG (1983), "Límites inferiores exponenciales para circuitos monótonos restringidos", Proc. 15º Simposio ACM sobre Teoría de la Computación , págs. 110-117, doi : 10.1145 / 800061.808739 , ISBN 0-89791-099-0, S2CID 6326587.
- Vassilevska, V .; Williams, R. (2009), "Encontrar, minimizar y contar subgrafos ponderados", Proc. 41º Simposio ACM sobre Teoría de la Computación , págs. 455–464, CiteSeerX 10.1.1.156.345 , doi : 10.1145 / 1536414.1536477 , ISBN 978-1-60558-506-2, S2CID 224579.
- Wegener, I. (1988), "Sobre la complejidad de los programas de ramificación y árboles de decisión para funciones de camarilla", Journal of the ACM , 35 (2): 461–472, doi : 10.1145 / 42282.46161 , S2CID 11967153.
- Yuster, R. (2006), "Encontrar y contar camarillas y conjuntos independientes en r- hipergráficos uniformes", Information Processing Letters , 99 (4): 130-134, doi : 10.1016 / j.ipl.2006.04.005.
- Zuckerman, D. (2006), "Extractores de grados lineales y la falta de aproximación de la camarilla máxima y el número cromático", Proc. 38th ACM Symp. Teoría de la Computación , págs. 681–690, doi : 10.1145 / 1132516.1132612 , ISBN 1-59593-134-1, S2CID 5713815 , ECCC TR05-100.