Problema de camarilla
Tarea de cálculo de subgrafos completos

El algoritmo de fuerza bruta encuentra una camarilla de 4 en este gráfico de 7 vértices (el complemento del gráfico de ruta de 7 vértices ) al verificar sistemáticamente que todos los subgráficos de 4 vértices C (7,4) = 35 estén completos.

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 grafo . Tiene varias formulaciones diferentes según qué camarillas y qué información sobre las camarillas se deba 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 grafo ponderado, enumerar todas las camarillas máximas (camarillas que no se pueden ampliar) y resolver el problema de decisión de probar si un grafo contiene una camarilla mayor 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 conocidos mutuos. 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 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-completos 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 grafos con exponencialmente muchos camarillas máximas. Por lo tanto, gran parte de la teoría sobre el problema de la camarilla está dedicada a identificar tipos especiales de grafos que admitan algoritmos más eficientes, o a establecer la dificultad computacional del problema general en varios modelos de computación.

Para encontrar un grupo máximo, se pueden inspeccionar sistemáticamente todos los subconjuntos, pero este tipo de búsqueda por fuerza bruta consume demasiado tiempo como para ser práctica en redes que comprenden más de unas pocas docenas de vértices. Aunque no se conoce ningún algoritmo de tiempo polinomial para este problema, se conocen algoritmos más eficientes que la búsqueda por fuerza bruta. Por ejemplo, el algoritmo de Bron-Kerbosch se puede utilizar para enumerar todos los grupos máximos en el tiempo óptimo del peor caso, y también es posible enumerarlos en tiempo polinomial por grupo.

Historia y aplicaciones

El estudio de los subgrafos completos en matemáticas es anterior a la terminología de "camarilla". Por ejemplo, los subgrafos completos aparecen en la literatura matemática en la reformulación de la teoría de Ramsey en teoría de grafos por Erdős y Szekeres (1935). Pero el término "camarilla" y el problema de enumerar camarillas mediante algoritmos provienen de las ciencias sociales, donde los subgrafos completos se utilizan para modelar camarillas sociales , grupos de personas que se conocen entre sí. Luce y Perry (1949) utilizaron grafos 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 estaban motivados por la aplicación sociológica. Los investigadores de las ciencias sociales también han definido otros tipos de camarillas y camarillas máximas en las redes sociales, "subgrupos cohesivos" de personas o actores en la red que 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 grafo no dirigido cuyos bordes representan pares relacionados de actores de la red social y luego aplicando un algoritmo para el problema de las camarillas a este grafo. [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), un trabajo temprano 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 la NP-completitud y los resultados de intratabilidad relacionados para proporcionar una explicación matemática para la dificultad percibida del problema de la camarilla. En la década de 1990, una serie de artículos innovadores que comenzaron con Feige et al. (1991) mostraron que (suponiendo que P ≠ NP ) ni siquiera es posible aproximar el problema con precisión y eficiencia.

Los algoritmos de búsqueda de camarillas se han utilizado en química para encontrar sustancias químicas que coincidan con una estructura objetivo [3] y para modelar el acoplamiento molecular y los sitios de unión de las reacciones químicas. [4] También se pueden utilizar para encontrar estructuras similares dentro de diferentes moléculas. [5] En estas aplicaciones, se forma un gráfico en el que cada vértice representa un par de átomos coincidentes, uno de cada una de dos moléculas. Dos vértices están conectados por una arista 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 coincidentes en el que todas las coincidencias son compatibles entre sí. [6] 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 común máximo de dos gráficos al problema de encontrar una camarilla máxima en su producto. [7]

En la generación automática de patrones de prueba , encontrar camarillas puede ayudar a limitar el tamaño de un conjunto de prueba. [8] En bioinformática , se han utilizado algoritmos de búsqueda de camarillas para inferir árboles evolutivos , [9] predecir estructuras de proteínas , [10] y encontrar grupos de proteínas que interactúan estrechamente. [11] Enumerar las camarillas en un gráfico de dependencia es un paso importante en el análisis de ciertos procesos aleatorios. [12] 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. [13]

Definiciones

El gráfico mostrado tiene una camarilla máxima, el triángulo {1,2,5}, y cuatro camarillas máximas más, los pares {2,3}, {3,4}, {4,5} y {4,6}.

Un grafo no dirigido está formado por un conjunto finito de vértices y un conjunto de pares de vértices no ordenados, que se denominan aristas . Por convención, en el análisis de algoritmos, el número de vértices del grafo se denota por n y el número de aristas se denota por m . Una camarilla en un grafo G es un subgrafo completo de G. Es decir, es un subconjunto K de los vértices tal que cada dos vértices en K son los dos puntos finales de una arista en G. Una camarilla maximal es una camarilla a la que no se pueden añadir más vértices. Para cada vértice v que no forma parte de una camarilla maximal, debe haber otro vértice w que esté en la camarilla y no sea adyacente a v , lo que impide que v se añada a la camarilla. Una camarilla máxima es una camarilla que incluye el mayor número posible de vértices. El número de camarilla ω ( G ) es el número de vértices en una camarilla máxima de G. [1]

Se han estudiado varios problemas de búsqueda de camarillas estrechamente relacionados. [14]

  • En el problema de camarilla máxima, la entrada es un grafo no dirigido y la salida es una camarilla máxima en el grafo. Si hay múltiples camarillas máximas, se puede elegir una de ellas arbitrariamente. [14]
  • En el problema de la camarilla máxima ponderada, la entrada es un grafo no dirigido con pesos en sus vértices (o, con menor frecuencia, en las aristas) y la salida es una camarilla con el máximo peso total. El problema de la camarilla máxima es el caso especial en el que todos los pesos son iguales. [15] Además del problema de optimizar la suma de pesos, también se han estudiado otros problemas de optimización de bicriterios más complicados. [16]
  • En el problema de lista de camarillas máximas, la entrada es un grafo no dirigido y la salida es una lista de todas sus camarillas máximas. El problema de camarillas máximas se puede resolver utilizando como subrutina un algoritmo para el problema de lista de camarillas máximas, porque la camarilla máxima debe estar incluida entre todas las camarillas máximas. [17]
  • En el problema de las k -cliques, la entrada es un grafo no dirigido y un número k . La salida es una clique con k vértices, si existe, o un valor especial que indica que no hay k -cliques en caso contrario. En algunas variaciones de este problema, la salida debe incluir todas las cliques de tamaño k . [18]
  • 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 una camarilla k , y falso en caso contrario. [19]

Los primeros cuatro de estos problemas son importantes en aplicaciones prácticas. El problema de decisión de camarilla no tiene importancia práctica; se formula de esta manera para aplicar la teoría de NP-completitud a problemas de búsqueda de camarillas. [19]

El problema de la camarilla y el problema de los conjuntos independientes son complementarios: una camarilla en G es un conjunto independiente en el grafo complementario de G y viceversa. [20] Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los dos problemas, y algunos artículos de investigación no distinguen claramente entre los dos problemas. Sin embargo, los dos problemas tienen diferentes propiedades cuando se aplican a familias restringidas de grafos. Por ejemplo, el problema de la camarilla puede resolverse en tiempo polinomial para grafos planares [21] mientras que el problema de los conjuntos independientes sigue siendo NP-hard en grafos planares. [22]

Algoritmos

Encontrar una única camarilla máxima

Una camarilla maximal , a veces llamada maximal de inclusión, es una camarilla que no está incluida en una camarilla más grande. Por lo tanto, cada camarilla está contenida en una camarilla maximal. [23] Las camarillas maximal pueden ser muy pequeñas. Un grafo puede contener una camarilla no maximal con muchos vértices y una camarilla separada de tamaño 2 que es maximal. Si bien una camarilla máxima (es decir, la más grande) es necesariamente maximal, lo inverso no se cumple. Hay algunos tipos de grafos en los que cada camarilla maximal es máxima; estos son los complementos de los grafos bien cubiertos , en los que cada conjunto independiente maximal es máximo. [24] Sin embargo, otros grafos tienen camarillas maximal que no son máximas.

Se puede encontrar una única camarilla máxima mediante un algoritmo voraz sencillo . 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 haciendo un bucle a través de los vértices restantes del grafo. Para cada vértice v que este bucle examina, agregue v a la camarilla si es adyacente a cada vértice que ya está en la camarilla, y descarte v en caso contrario. Este algoritmo se ejecuta en tiempo lineal . [25] Debido a la facilidad de encontrar camarillas máximas y su tamaño potencialmente 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 de otro modo 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 encontrada por el algoritmo anterior) es completo para la clase de funciones de tiempo polinomial . Este resultado implica que es poco probable que el problema sea solucionable dentro de la clase de complejidad paralela NC . [26]

Camarillas de tamaño fijo

Se puede comprobar si un grafo 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. Lleva tiempo O ( n k  k 2 ) , como se expresa utilizando la notación O grande . Esto se debe a que hay O ( n k ) subgrafos para comprobar, cada uno de los cuales tiene O ( k 2 ) aristas cuya presencia en G necesita ser comprobada. 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. [27]

El caso no trivial más simple del problema de búsqueda de camarillas es encontrar un triángulo en un grafo o, equivalentemente, determinar si el grafo está libre de triángulos . En un grafo G con m aristas, puede haber como máximo Θ( m 3/2 ) triángulos (usando la notación theta grande para indicar que este límite es estricto). 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 ) tiempo en el peor caso (usando la notación omega grande ), y se conocen algoritmos que coinciden con este límite de tiempo. [28] Por ejemplo, Chiba y Nishizeki (1985) describen un algoritmo que ordena los vértices en orden desde el grado más alto al más bajo 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 anterior en la lista. Para ello, 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 puntos finales marcados y, a continuación, elimina 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 (denotada a ( G ) ) multiplicada por el número de bordes, que es O ( m  a ( G )) . Dado que la arboricidad es como máximo O ( m 1/2 ) , este algoritmo se ejecuta en un tiempo O ( m 3/2 ) . De forma más general, todas las camarillas de k -vértices se pueden enumerar mediante un algoritmo similar que tarda un tiempo proporcional al número de bordes multiplicado por la arboricidad a la potencia ( k  − 2 ) . Para gráficos de arboricidad constante, como los gráficos planares (o en general los gráficos de cualquier familia de gráficos menores cerrados no triviales ), este algoritmo toma un tiempo O ( m ) , lo cual es óptimo ya que es lineal en el tamaño de la entrada. [18]

Si se desea un solo triángulo, o una garantía de que el gráfico está libre de 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 de multiplicación de matrices rápidas para encontrar triángulos en 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 de matrices rápida también se han extendido a problemas de búsqueda de k -cliques para valores mayores de k . [29]

Listado de todas las camarillas máximas

Por un resultado de Moon y Moser (1965), cada grafo de n vértices tiene como máximo 3 n /3 camarillas máximas. Se pueden enumerar mediante el algoritmo de Bron-Kerbosch , un procedimiento de retroceso recursivo de Bron y 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 deberían agregarse nuevamente. 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 ) , que coincide con el número de camarillas que podría ser necesario enumerar. [30] Por lo tanto, esto proporciona una solución óptima en el peor de los casos al problema de enumerar todos los grupos máximos. Además, se ha informado ampliamente que el algoritmo de Bron-Kerbosch es más rápido en la práctica que sus alternativas. [31]

Sin embargo, cuando el número de camarillas es significativamente menor que su peor caso, otros algoritmos pueden ser preferibles. Como Tsukiyama et al. (1977) demostraron, también es posible enumerar todas las camarillas máximas en un grafo en una cantidad de tiempo que es polinómica 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 un algoritmo sensible a la salida . Su algoritmo se basa en las siguientes dos observaciones, que relacionan las camarillas máximas del grafo dado G con las camarillas máximas de un grafo G  \  v formado al eliminar un vértice arbitrario v de G :

  • Para cada camarilla máxima K de G  \  v , o bien K continúa formando una camarilla máxima en G , o bien K  ⋃ { v } forma una 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 a v es una camarilla máxima en G  \  v , y cada camarilla máxima en G que sí contiene a v puede formarse a partir de una camarilla máxima K en G  \  v agregando v y quitando los no vecinos de v de K .

Usando estas observaciones pueden generar todos los cliques maximales en G por un algoritmo recursivo que elige un vértice v arbitrariamente y luego, para cada clique maximal K en G  \  v , produce tanto K como el clique formado sumando v a K y eliminando los no vecinos de v . Sin embargo, algunos cliques de G pueden generarse de esta manera a partir de más de un clique padre de G  \  v , por lo que eliminan duplicados produciendo un clique en G solo cuando su padre en G  \  v es lexicográficamente máximo entre todos los cliques padres posibles. Sobre la base de este principio, muestran que todos los cliques maximales en G pueden generarse en tiempo O ( mn ) por clique, 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 clique, donde a es la arboricidad del grafo dado. Makino y Uno (2004) ofrecen 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 todos los grupos máximos en orden lexicográfico con un retardo polinomial por grupo. Sin embargo, la elección del orden es importante para la eficiencia de este algoritmo: para el orden inverso, no existe un algoritmo de retardo polinomial a menos que P = NP .

Sobre la base de este resultado, es posible enumerar todos los cliques máximos en tiempo polinomial, para familias de grafos en las que el número de cliques está acotado polinomialmente. Estas familias incluyen grafos cordales , grafos completos , grafos sin triángulos , grafos de intervalo , grafos de boxicidad acotada y grafos planares . [32] En particular, los grafos planares tienen O ( n ) cliques, de tamaño constante como máximo, que pueden enumerarse en tiempo lineal. Lo mismo es cierto para cualquier familia de grafos que sea dispersa (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 subgrafos. [18] [33]

Encontrar el máximo de camarillas en gráficos arbitrarios

Es posible encontrar la camarilla máxima, o el número de camarillas, de un grafo arbitrario de n vértices en 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 grafo y devolver la 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 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 ) , 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 precalcula para todos los subgrafos pequeños conectados del grafo de complemento . Estas soluciones parciales se utilizan para acortar la recursión de retroceso. El algoritmo más rápido conocido hoy en día es una versión refinada de este método de Robson (2001) que se ejecuta en un tiempo O (2 0.249 n ) = O (1.1888 n ) . [34]

También se han realizado investigaciones exhaustivas 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 acotación , [35] búsqueda local , [36] algoritmos voraces , [37] y programación de restricciones . [38] Las metodologías informáticas no estándar que se han sugerido para encontrar camarillas incluyen la computación de ADN [39] y la computación cuántica adiabática . [40] El problema de la camarilla máxima fue objeto de un desafío de implementación patrocinado por DIMACS en 1992-1993, [41] y una colección de gráficos utilizados como puntos de referencia para el desafío, que está disponible públicamente. [42]

Clases especiales de gráficos

En este gráfico de permutación , las camarillas máximas corresponden a las subsecuencias decrecientes más largas (4,3,1) y (4,3,2) de la permutación definitoria.

Los grafos planares y otras familias de grafos dispersos se han analizado anteriormente: tienen linealmente muchos camarillas máximas, de tamaño acotado, que pueden enumerarse en tiempo lineal. [18] En particular, para los grafos planares, cualquier camarilla puede tener como máximo cuatro vértices, según el teorema de Kuratowski . [21]

Los grafos perfectos se definen por las propiedades de que su número de clique es igual a su número cromático , y que esta igualdad se cumple también en cada uno de sus subgrafos inducidos . Para grafos perfectos, es posible encontrar un clique máximo en tiempo polinomial, utilizando un algoritmo basado en programación semidefinida . [43] Sin embargo, este método es complejo y no combinatorio, y se han desarrollado algoritmos especializados de búsqueda de clique para muchas subclases de grafos perfectos. [44] En los grafos complementarios de grafos bipartitos , el teorema de Kőnig permite resolver el problema de clique máximo utilizando técnicas de emparejamiento . En otra clase de grafos perfectos, los grafos de permutación , un clique máximo es una subsecuencia decreciente más larga de la permutación que define el grafo y se puede encontrar utilizando algoritmos conocidos para el problema de la subsecuencia decreciente más larga. Por el contrario, cada instancia del problema de la subsecuencia decreciente más larga se puede describir de manera equivalente como un problema de encontrar una camarilla máxima en un gráfico de permutación. [45] Incluso, Pnueli y Lempel (1972) proporcionan un algoritmo de tiempo cuadrático alternativo para camarillas máximas 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. [46] En los gráficos cordales , las camarillas máximas se pueden encontrar enumerando los vértices en un orden de eliminación y verificando los vecindarios de camarilla de cada vértice en este orden. [47]

En algunos casos, estos algoritmos pueden extenderse también a otras clases de grafos no perfectos. Por ejemplo, en un grafo circular , el vecindario de cada vértice es un grafo de permutación, por lo que se puede encontrar una camarilla máxima en un grafo circular aplicando el algoritmo del grafo de permutación a cada vecindario. [48] De manera similar, en un grafo de disco unitario (con una representación geométrica conocida), existe un algoritmo de tiempo polinomial para camarillas máximas basado en la aplicación del algoritmo para complementos de grafos bipartitos a vecindarios compartidos de pares de vértices. [49]

Un gráfico aleatorio con una camarilla plantada

El problema algorítmico de encontrar una camarilla máxima en un grafo aleatorio extraído del modelo de Erdős–Rényi (en el que cada arista aparece con probabilidad 1/2 , independientemente de las otras aristas) fue sugerido por Karp (1976). Debido a que la camarilla máxima en un grafo 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 . [50] Aunque el número de camarillas de tales grafos suele ser muy cercano a 2 log 2 n , los algoritmos codiciosos simples , así como las técnicas de aproximación aleatoria 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 grafos es con alta probabilidad exponencial en log 2 n , lo que impide que los métodos que enumeran todas las camarillas máximas se ejecuten en tiempo polinomial. [51] 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 camarillas grandes. [52] Si bien los métodos espectrales [53] y la programación semidefinida [54] pueden detectar camarillas ocultas de tamaño Ω( √ n ) , actualmente no se conocen algoritmos de tiempo polinomial que detecten aquellas de tamaño o ( √ n ) (expresado utilizando la notación little-o ). [55]

Algoritmos de aproximación

Varios autores han considerado algoritmos de aproximación que intentan encontrar una camarilla o conjunto independiente que, aunque no sea máximo, tenga un tamaño lo más cercano al máximo que se puede encontrar en tiempo polinomial. Aunque gran parte de este trabajo se ha centrado en conjuntos independientes en grafos 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 escasez. [56]

Feige (2004) describe un algoritmo de tiempo polinomial que encuentra una camarilla de tamaño Ω((log  n /log log  n ) 2 ) en cualquier grafo que tenga número de camarilla Ω( n /log k n ) para cualquier constante k . Al usar este algoritmo cuando el número de camarilla de un grafo de entrada dado está entre n /log  n y n /log 3 n , cambiar a un algoritmo diferente de Boppana & Halldórsson (1992) para grafos con números de camarilla más altos y elegir una camarilla de dos 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 mejor conocido hasta la fecha. [57] Los resultados sobre la dureza de la aproximación que se describen a continuación sugieren que no puede haber ningún algoritmo de aproximación con una relación de aproximación significativamente menor que la lineal.

Límites inferiores

NP-completitud

La instancia de satisfacibilidad de 3-CNF (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) se redujo a Clique. Los vértices verdes forman un 3-clique y corresponden a una asignación satisfactoria. [58]

El problema de decisión de camarilla es NP-completo . Fue uno de los 21 problemas originales de Richard Karp que se mostraron NP-completos en su artículo de 1972 "Reducibilidad entre problemas combinatorios". [59] Este problema también se mencionó en el artículo de Stephen Cook que presenta la teoría de problemas NP-completos. [60] Debido a la dificultad 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 NP-completitud de Karp es una reducción de muchos-uno del problema de satisfacibilidad booleano . Describe cómo traducir fórmulas booleanas en forma normal conjuntiva (CNF) en instancias equivalentes del problema de máxima camarilla. [61] La satisfacibilidad, a su vez, se demostró NP-completa en el teorema de Cook-Levin . A partir de una fórmula CNF dada, Karp forma un grafo que tiene un vértice para cada par ( v , c ) , donde v es una variable o su negación y c es una cláusula en la fórmula que contiene a v . Dos de estos vértices están conectados por una arista 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 sean negaciones entre sí. Si k denota el número de cláusulas en la fórmula CNF, entonces las camarillas de k vértices 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 satisfacible si y solo si existe una camarilla de k vértices. [59]

Algunos problemas NP-completos (como el problema del viajante de comercio en grafos planares ) 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. [62] Sin embargo, es poco probable que un límite de tiempo subexponencial de este tipo sea posible para el problema de la camarilla en grafos arbitrarios, ya que implicaría límites subexponenciales similares para muchos otros problemas NP-completos estándar. [63]

Complejidad del circuito

Un circuito monótono para detectar una k -clique en un gráfico de n vértices para k  = 3 y n  = 4. Cada entrada del circuito codifica la presencia o ausencia de un borde particular (rojo) en el gráfico. El circuito utiliza una compuerta interna para detectar cada k -clique potencial.

La dificultad computacional del problema de la camarilla ha llevado a que se lo 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 grafo monótono , lo que significa que, si existe una camarilla en un grafo dado, existirá en cualquier supergrafo . Debido a que esta propiedad es monótona, debe existir un circuito monótono, que use solo puertas y y puertas o , para resolver el problema de decisión de camarilla para un tamaño de camarilla fijo dado. Sin embargo, se puede demostrar que el tamaño de estos circuitos es una función superpolinómica 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. [64] Incluso si se permite un pequeño número de puertas NOT , la complejidad sigue siendo superpolinómica. [65] Además, la profundidad de un circuito monótono para el problema de la camarilla que usa puertas de abanico de entrada acotado debe ser al menos un polinomio en el tamaño de la camarilla. [66]

Complejidad del árbol de decisiones

Un árbol de decisión simple para detectar la presencia de una clique de 3 en un gráfico de 4 vértices. Utiliza hasta 6 preguntas del tipo "¿Existe el borde rojo?", que coinciden con el límite óptimo n ( n  − 1)/2.

La complejidad (determinista) del árbol de decisión para determinar una propiedad de un grafo es el número de preguntas de la forma "¿Existe 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 grafo 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 para ser realizadas. Por lo tanto, cualquier propiedad de un grafo puede determinarse 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 una entrada del peor caso) que un algoritmo aleatorio o cuántico necesita haber respondido para determinar correctamente si el grafo dado tiene la propiedad. [67]

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ótona no trivial es exactamente n ( n  − 1)/2 . Para propiedades de grafo monótonas arbitrarias, esta conjetura sigue sin demostrarse. Sin embargo, para árboles de decisión deterministas, y para cualquier k en el rango 2 ≤ k ≤ n , Bollobás (1976) demostró que la propiedad de contener una k -camarilla tiene una complejidad de árbol de decisión exactamente n ( n  − 1)/2 . 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 acotado. [68]

La conjetura de Aanderaa–Karp–Rosenberg también establece que la complejidad del árbol de decisión aleatorio de funciones monótonas no triviales es Θ( n 2 ) . La conjetura nuevamente permanece sin demostrar, pero se ha resuelto para 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 ) . [69] Para los árboles de decisión cuánticos, el límite inferior más conocido es Ω( n ) , pero no se conoce ningún algoritmo de coincidencia para el caso de k ≥ 3 . [70]

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 pequeño parámetro entero k y para los cuales el problema se vuelve más difícil a medida que k aumenta, como encontrar k -cliques en grafos. Se dice que un problema es manejable con parámetros fijos si existe un algoritmo para resolverlo en entradas de tamaño n y una función f , tal que el algoritmo se ejecuta en el tiempo f ( k )  n O (1) . Es decir, es manejable 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 . [71]

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 una multiplicación rápida de matrices , el tiempo de ejecución aún 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 la manejabilidad con parámetros fijos. Downey y Fellows (1995) definieron una jerarquía de problemas parametrizados, la jerarquía W, que conjeturaron que no tenía algoritmos manejables con parámetros fijos. Probaron que el conjunto independiente (o, equivalentemente, camarilla) es difícil para el primer nivel de esta jerarquía, W[1] . Por lo tanto, según su conjetura, la camarilla no tiene un algoritmo manejable con 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. [72]

Chen et al. (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 con parámetros fijos. [73]

Aunque es poco probable que los problemas de enumerar camarillas máximas o de encontrar camarillas máximas sean manejables con parámetros fijos con el parámetro k , pueden ser manejables con parámetros fijos para otros parámetros de complejidad de instancia. Por ejemplo, se sabe que ambos problemas son manejables con parámetros fijos cuando se parametrizan por la degeneración del gráfico de entrada. [33]

Dureza de aproximación

Un gráfico de relaciones de compatibilidad entre muestras de 2 bits de cadenas de prueba de 3 bits. Cada clique (triángulo) máximo en este gráfico representa todas las formas de muestrear una única cadena de 3 bits. La prueba de inaproximabilidad del problema de clique implica subgrafos inducidos de grafos definidos de forma análoga para cantidades mayores de bits.

Hace tiempo que se conocen resultados débiles que sugieren que el problema de la camarilla podría ser difícil de aproximar. Garey y Johnson (1978) observaron que, debido a que el número de camarilla toma valores enteros pequeños y es NP-difícil de calcular, no puede tener un esquema de aproximación de tiempo polinomial completo , a menos que P = NP. Si se dispusiera de una aproximación demasiado precisa, redondear su valor a un entero daría el número de camarilla exacto. Sin embargo, se sabía poco más hasta principios de la década de 1990, cuando varios autores comenzaron a hacer conexiones entre la aproximación de camarillas máximas y pruebas probabilísticamente comprobables . Utilizaron estas conexiones para demostrar la dureza de los resultados de aproximación para el problema de la camarilla máxima. [74] Después de muchas mejoras a estos resultados, ahora se sabe que, para cada número real ε  > 0 , no puede haber un algoritmo de tiempo polinomial que aproxime la camarilla máxima dentro de un factor mejor que O ( n 1 −  ε ) , a menos que P = NP . [75]

La idea básica de estos resultados de inaproximabilidad es formar un gráfico que represente un sistema de prueba probabilísticamente comprobable para un problema NP-completo como el problema de satisfacibilidad booleano. En un sistema de prueba probabilísticamente comprobable, una prueba se representa como una secuencia de bits. Una instancia del problema de satisfacibilidad debería tener una prueba válida si y solo si es satisfacible. La prueba se comprueba mediante un algoritmo que, después de un cálculo en tiempo polinomial sobre la entrada al problema de satisfacibilidad, elige examinar una pequeña cantidad de posiciones elegidas aleatoriamente 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 inválida. Para cada prueba inválida, la probabilidad de que el verificador la acepte debe ser baja. [76]

Para transformar un sistema de prueba probabilísticamente comprobable de este tipo en un problema de camarilla, se forma un grafo con un vértice para cada posible ejecución de aceptación del verificador 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 bit para aquellas posiciones que harían que el verificador aceptara la prueba. Puede representarse 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 grafo, si las dos ejecuciones de aceptación correspondientes ven los mismos valores de bit en cada posición que ambas examinan. Cada cadena de prueba (válida o no) corresponde a una camarilla, el conjunto de ejecuciones 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 de pruebas aceptan. Si la instancia de satisfacibilidad original es satisfacible, tendrá una cadena de prueba válida, una que sea aceptada por todas las ejecuciones del verificador, y esta cadena corresponderá a una camarilla grande en el grafo. Sin embargo, si la instancia original no es satisfacible, entonces todas las cadenas de prueba son inválidas, cada cadena de prueba tiene solo una pequeña cantidad de ejecuciones del verificador que la aceptan por error, y todas las camarillas son pequeñas. Por lo tanto, si uno pudiera distinguir en tiempo polinomial entre grafos que tienen camarillas grandes y grafos en los que todas las camarillas son pequeñas, o si uno pudiera aproximarse con precisión al problema de la camarilla, entonces aplicar esta aproximación a los grafos generados a partir de instancias de satisfacibilidad permitiría distinguir las instancias satisfacibles de las instancias no satisfacibles. Sin embargo, esto no es posible a menos que P = NP. [76]

Notas

  1. ^ abc Bomze y otros (1999); Gutin (2004).
  2. ^ Wasserman y Faust (1994).
  3. ^ Rhodes y otros (2003).
  4. ^ Kuhl, Crippen y Friesen (1983).
  5. ^ Comité del Consejo Nacional de Investigación sobre los Desafíos Matemáticos de la Química Computacional (1995). Véanse en particular las páginas 35 y 36.
  6. ^ Muegge y Rarey (2001). Véanse en particular las págs. 6 y 7.
  7. ^ Barrow y Burstall (1976).
  8. ^ Hamzaoglu y Patel (1998).
  9. ^ Día y Sankoff (1986).
  10. ^ Samudrala y Moult (1998).
  11. ^ Spirin y Mirny (2003).
  12. ^ Frank y Strauss (1986).
  13. ^ El gráfico de Keller utilizado por Lagarias y Shor (1992) tiene 1048576 vértices y un tamaño de camarilla de 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 prueba al encontrar una camarilla de tamaño 256 en un gráfico de Keller de 65536 vértices.
  14. ^ ab Valiente (2002); Pelillo (2009).
  15. ^ Pelillo (2009).
  16. ^ Sethuraman y Butenko (2015).
  17. ^ Valiente (2002).
  18. ^ abcd Chiba y Nishizeki (1985).
  19. ^ desde Cormen y col. (2001).
  20. ^ Cormen et al. (2001), Ejercicio 34-1, pág. 1018.
  21. ^ ab Papadimitriou y Yannakakis (1981); Chiba y Nishizeki (1985).
  22. ^ Garey, Johnson y Stockmeyer (1976).
  23. ^ Véase, por ejemplo, Frank y Strauss (1986).
  24. ^ Plummer (1993).
  25. ^ Skiena (2009), pág. 526.
  26. ^ Cocinar (1985).
  27. ^ Véase, por ejemplo, Downey & Fellows (1995).
  28. ^ Itai y Rodeh (1978) proporcionan un algoritmo con un tiempo de ejecución de 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 un tiempo O ( m 3/2 ) .
  29. ^ Eisenbrand y Grandoni (2004); Kloks, Kratsch y Müller (2000); Nešetřil y Poljak (1985); Vassilevska y Williams (2009); Yuster (2006).
  30. ^ Tomita, Tanaka y Takahashi (2006).
  31. ^ Cazals y Karande (2008); Eppstein, Löffler y Strash (2013).
  32. ^ Rosgen y Stewart (2007).
  33. ^ por Eppstein, Löffler y Strash (2013).
  34. ^ Robson (2001).
  35. ^ Balas y Yu (1986); Carraghan y Pardalos (1990); Párdalos y Rogers (1992); Östergard (2002); Fahle (2002); Tomita y Seki (2003); Tomita y Kameda (2007); Konc y Janežič (2007).
  36. ^ Battiti y Protasi (2001); Katayama, Hamamoto y Narihisa (2005).
  37. ^ Abello, Pardalos y Resende (1999); Grosso, Locatelli y Della Croce (2004).
  38. ^ Región (2003).
  39. ^ Ouyang et al. (1997). Aunque el título se refiere a camarillas máximas, el problema que este artículo resuelve es en realidad el problema de la camarilla máxima.
  40. ^ Childs y otros (2002).
  41. ^ Johnson y Trick (1996).
  42. ^ Gráficos de desafío DIMACS para el problema de la camarilla Archivado el 30 de marzo de 2018 en Wayback Machine , consultado el 17 de diciembre de 2009.
  43. ^ Grötschel, Lovász y Schrijver (1988).
  44. ^ Golumbic (1980).
  45. ^ Golumbic (1980), pág. 159.
  46. ^ Incluso, Pnueli y Lempel (1972).
  47. ^ Blair y Peyton (1993), Lema 4.5, pág. 19.
  48. ^ Gavril (1973); Golumbic (1980), pág. 247.
  49. ^ Clark, Colbourn y Johnson (1990).
  50. ^ Canción (2015).
  51. ^ Jerrum (1992).
  52. ^ Arora y Barak (2009), Ejemplo 18.2, págs. 362–363.
  53. ^ Alon, Krivelevich y Sudakov (1998).
  54. ^ Feige y Krauthgamer (2000).
  55. ^ Meka, Potechin y Wigderson (2015).
  56. ^ Boppana y Halldórsson (1992); Feige (2004); Halldórsson (2000).
  57. ^ Liu et al. (2015): "En términos de la cantidad de vértices en los grafos, Feige muestra la mejor relación de aproximación conocida actualmente". Liu et al. escriben sobre el conjunto independiente máximo , pero para fines de aproximación no hay diferencia entre los dos problemas.
  58. ^ Adaptado de Sipser (1996)
  59. ^ por Karp (1972).
  60. ^ Cocinar (1971).
  61. ^ Cook (1971) da esencialmente la misma reducción, de 3-SAT en lugar de Satisfacbilidad, para demostrar que el isomorfismo del subgrafo es NP-completo.
  62. ^ Lipton y Tarjan (1980).
  63. ^ Impagliazzo, Paturi y Zane (2001).
  64. ^ Alon y Boppana (1987). Para límites más débiles y anteriores sobre circuitos monótonos para el problema de la camarilla, véase Valiant (1983) y Razborov (1985).
  65. ^ Amano y Maruoka (2005).
  66. ^ Goldmann y Håstad (1992) utilizaron la complejidad de la comunicación para demostrar este resultado.
  67. ^ Véase Arora y Barak (2009), Capítulo 12, "Árboles de decisión", págs. 259-269.
  68. ^ Wegener (1988).
  69. ^ Por ejemplo, esto se desprende de Gröger (1992).
  70. ^ Childs y Eisenberg (2005); Magniez, Santha y Szegedy (2007).
  71. ^ Downey & Fellows (1999). Técnicamente, suele haber un requisito adicional de que f sea una función computable .
  72. ^ Downey y Fellows (1995).
  73. ^ Chen y otros (2006).
  74. ^ Feige y otros. (1991); Arora y Safra (1998); Arora et al. (1998).
  75. ^ Håstad (1999) demostró la inaproximabilidad de esta relación utilizando un supuesto teórico de complejidad más fuerte, la desigualdad de NP y ZPP . Khot (2001) describió con mayor precisión la relación de inaproximabilidad, pero con un supuesto aún más fuerte. Zuckerman (2006) desaleatorizó la construcción debilitando su supuesto a P ≠ NP.
  76. ^ ab Esta reducción se debe originalmente a Feige et al. (1991) y se utilizó en todas las pruebas de inaproximabilidad posteriores; las pruebas difieren en las fortalezas y los detalles de los sistemas de pruebas probabilísticamente comprobables en los que se basan.

Referencias

Encuestas y libros de texto

Artículos de investigación

  • Abello, J.; Pardalos, PM; Resende, MGC (1999), "Sobre problemas de camarilla máxima en grafos muy grandes" (PDF) , en Abello, J.; Vitter, J. (eds.), External Memory Algorithms , Serie DIMACS sobre Matemáticas Discretas y Ciencias de la Computación Teórica, vol. 50, American Mathematical Society , págs. 119–130, ISBN 0-8218-1184-3, archivado desde el original (PDF) el 16 de enero de 2017 , consultado el 13 de enero de 2017.
  • 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.
  • Alón, 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 determinados", Actas del 2º Simposio Europeo sobre 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)log log N puertas de negació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 pruebas y dureza de los problemas de aproximación", Journal of the ACM , 45 (3): 501–555, doi :10.1145/278298.278306, S2CID  8561542, ECCC  TR98-008Presentado originalmente en el Simposio sobre Fundamentos de la Ciencia de la Computación de 1992 , doi :10.1109/SFCS.1992.267823.
  • Arora, S. ; Safra, S. (1998), "Verificació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  751563Presentado originalmente en el Simposio sobre Fundamentos de la Ciencia de la Computación de 1992 , 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 subgrafos, 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 máxima camarilla", Algorithmica , 29 (4): 610–637, doi :10.1007/s004530010074, S2CID  1800512.
  • Bollobás, Béla (1976), "Los subgrafos completos son elusivos", 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 mediante la exclusión de subgrafos", BIT Numerical Mathematics , 32 (2): 180–196, doi :10.1007/BF01994876, S2CID  123335474.
  • Bron, C.; Kerbosch, J. (1973), "Algoritmo 457: búsqueda de todas las camarillas de un grafo no dirigido", Communications of the ACM , 16 (9): 575–577, doi : 10.1145/362342.362367 , S2CID  13886709.
  • Carraghan, R.; Pardalos, PM (1990), "Un algoritmo exacto para el problema de camarilla máxima", Operations Research Letters , 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 camarillas máximas", Theoretical Computer Science , 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), "Algoritmos de arboricidad y listado de subgrafos", SIAM Journal on Computing , 14 (1): 210–223, doi :10.1137/0214017, S2CID  207051803.
  • Childs, AM; Farhi, E.; Goldstone, J .; Gutmann, S. (2002), "Encontrar camarillas mediante evolución adiabática cuántica", Quantum Information and Computation , 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", Quantum Information and Computation , 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), "Gráficos de disco unitario", 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. 3rd ACM Symposium on Theory of Computing , 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.
  • Day, William HE; Sankoff, David (1986), "Complejidad computacional de la inferencia de filogenias por compatibilidad", Systematic Zoology , 35 (2): 224–229, doi :10.2307/2413432, JSTOR  2413432.
  • Downey, RG; Fellows, MR (1995), "Tratabilidad y completitud de parámetros fijos. II. Sobre 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", Theoretical Computer Science , 326 (1–3): 57–67, doi : 10.1016/j.tcs.2004.05.009.
  • Eppstein, David ; Löffler, Martín; Strash, Darren (2013), "Listado de todas las camarillas máximas en gráficos grandes y 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.
  • Even, S. ; Pnueli, A. ; Lempel, A. (1972), "Gráficos de permutación y grafos transitivos", Journal of the ACM , 19 (3): 400–410, doi : 10.1145/321707.321710 , S2CID  9501737.
  • Fahle, T. (2002), "Simple y rápido: Mejorar un algoritmo de ramificación y acotación para un grupo máximo", Proc. 10.º Simposio Europeo sobre Algoritmos , Lecture Notes in Computer Science, vol. 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 mediante la eliminación de 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), "La aproximación de clique es casi NP-completa", [1991] Actas del 32.º Simposio Anual de Fundamentos de la Ciencia de la Computación , págs. 2–12, doi :10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0, Número de identificación del sujeto  46605913.
  • Feige, U. ; Krauthgamer, R. (2000), "Encontrar y certificar una camarilla oculta grande en un gráfico semialeatorio", Random Structures and Algorithms , 16 (2): 195–208, doi :10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
  • Frank, Ove; Strauss, David (1986), "Gráficos de Markov", Revista de la Asociación Estadounidense de Estadística , 81 (395): 832–842, doi :10.2307/2289017, JSTOR  2289017, MR  0860518.
  • Garey, señor ; Johnson, DS (1978), "Resultados de completitud de NP "fuertes": motivación, ejemplos e implicaciones", Journal of the ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , S2CID  18371269.
  • Garey, MR ; Johnson, DS ; Stockmeyer, L. (1976), "Algunos problemas simplificados de gráficos NP-completos", Theoretical Computer Science , 1 (3): 237–267, doi : 10.1016/0304-3975(76)90059-1 , MR  0411240.
  • Gavril, F. (1973), "Algoritmos para un grupo máximo y un conjunto máximo independiente de un gráfico circular", Networks , 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 aleatoria de las propiedades de los grafos monótonos" (PDF) , Acta Cybernetica , 10 (3): 119–127, archivado desde el original (PDF) el 24 de septiembre de 2015 , consultado el 2 de octubre de 2009
  • Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Combinación de swaps y pesos de nodos en un enfoque adaptativo voraz para el problema de 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 subconjuntos hereditarios y conjuntos independientes ponderados", 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 prueba para circuitos combinacionales", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design , págs. 283–289, doi : 10.1145/288548.288615 , ISBN 1-58113-008-2, S2CID12258606 ​.
  • Harary, F. ; Ross, IC (1957), "Un procedimiento para la detección de camarillas utilizando la matriz de grupo", Sociometry , 20 (3), American Sociological Association: 205–215, doi :10.2307/2785673, JSTOR  2785673, MR  0110590.
  • Håstad, J. (1999), "Es difícil aproximar una camarilla 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 grafo", SIAM Journal on Computing , 7 (4): 413–423, doi :10.1137/0207033.
  • Jerrum, M. (1992), "Grandes camarillas eluden el proceso Metropolis", Random Structures and Algorithms , 3 (4): 347–359, doi :10.1002/rsa.3240030402.
  • Jian, T (1986), "Un algoritmo O (2 0.304 n ) para resolver el problema del conjunto independiente máximo", IEEE Transactions on Computers , 35 (9), IEEE Computer Society: 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, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 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), "Reducibility among combinatorial problems", en Miller, RE; Thatcher, JW (eds.), Complexity of Computer Computations (PDF) , Nueva York: Plenum , pp. 85–103, archivado desde el original (PDF) el 29 de junio de 2011 , consultado el 17 de diciembre de 2009.
  • Karp, Richard M. (1976), "Análisis probabilístico de algunos problemas de búsqueda combinatoria", en Traub, JF (ed.), Algoritmos y complejidad: nuevas direcciones y resultados recientes , 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 de gráficos aproximada", Actas del 42.º Simposio IEEE sobre fundamentos de la informática , págs. 600-609, doi :10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3, Número de identificación del sujeto  11987483.
  • Kloks, T.; Kratsch, D.; Müller, H. (2000), "Cómo encontrar y contar subgrafos inducidos pequeños 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 de ramificación y acotación mejorado para el problema de camarilla máxima" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (3): 569–590Có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, S2CID  122923018.
  • Lagarias, Jeffrey C. ; Shor, Peter W. (1992), "La conjetura de Keller sobre el teselado de cubos es falsa en dimensiones altas", Bulletin of the American Mathematical Society , New Series, 27 (2): 279–283, arXiv : math/9210222 , doi :10.1090/S0273-0979-1992-00318-X, MR  1155280, S2CID  6390600.
  • Lipton, RJ ; Tarjan, RE (1980), "Aplicaciones de un teorema separador planar", 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 independientes máximos en grafos masivos", Actas de la 41.ª Conferencia internacional sobre bases de datos muy grandes (VLDB 2015) (PDF) , Actas de la Fundación VLDB, vol. 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 de grupo", Psychometrika , 14 (2): 95–116, doi :10.1007/BF02289146, hdl : 10.1007/BF02289146 , PMID  18152948, S2CID  16186758.
  • Mackey, John (2002), "Un mosaico cúbico de dimensión ocho sin compartir caras", Geometría discreta y computacional , 28 (2): 275–279, doi : 10.1007/s00454-002-2801-9 , MR  1920144.
  • Magniez, Federico; Santa, 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", Algorithm Theory: SWAT 2004 (PDF) , Lecture Notes in Computer Science, vol. 3111, Springer-Verlag , págs. 260–272, CiteSeerX  10.1.1.138.705 , doi :10.1007/978-3-540-27810-8_23, ISBN 978-3-540-22339-9.
  • Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Límites inferiores de suma de cuadrados para la camarilla plantada", Actas del cuadragésimo séptimo simposio anual de la ACM 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, Número de identificación del sujeto  2754095.
  • Moon, JW; Moser, L. (1965), "Sobre camarillas en grafos", 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 camarilla máxima", Discrete Applied Mathematics , 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), "El problema de la camarilla para grafos planares", 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 ramificación y acotación para el problema de 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 al inglés en Sov. Math. Dokl. 31 (1985): 354–357{{citation}}: Mantenimiento de CS1: postscript ( enlace ).
  • Régin, J.-C. (2003), "Uso de programación con restricciones para resolver el problema de camarilla máxima", Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 , Lecture Notes in Computer Science, vol. 2833, Springer-Verlag , pp. 634–648, doi :10.1007/978-3-540-45193-8_43, ISBN 978-3-540-20202-8.
  • Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: búsqueda de similitudes en 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 independientes máximos", 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(2n/4).
  • Rosgen, B; Stewart, L (2007), "Resultados de complejidad en gráficos con pocas camarillas", Matemáticas discretas y ciencias de la computación teórica , 9 (1): 127–136.
  • Samudrala, Ram; Moult, John (1998), "Un algoritmo de teoría de grafos para el modelado comparativo de la estructura de proteínas", Journal of Molecular Biology , 279 (1): 287–302, doi :10.1006/jmbi.1998.1689, PMID  9636717.
  • Sethuraman, Samyukta; Butenko, Sergiy (2015), "El problema de la camarilla de proporción máxima", 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 los conjuntos independientes en grafos aleatorios", International Journal of Computer Mathematics , 92 (11): 2233–2242, doi :10.1080/00207160.2014.976210, S2CID  6713201.
  • Spirin, Victor; Mirny, Leonid A. (2003), "Complejos proteicos 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 independiente máximo" (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 acotación 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 ramificación y acotación para encontrar una camarilla máxima", Matemáticas discretas y ciencias de la computación teóricas , Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, págs. 278–289, doi :10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4, Número de identificación del sujeto  21436014.
  • Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "La complejidad temporal del peor caso para generar todas las camarillas máximas y experimentos computacionales", Theoretical Computer Science , 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, Número de identificación del sujeto  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, S2CID224579 ​.
  • 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 hipergrafos r -uniformes", Information Processing Letters , 99 (4): 130–134, doi :10.1016/j.ipl.2006.04.005.
  • Zuckerman, D. (2006), "Extractores de grado lineal y la inaproximabilidad de la clique máxima y el número cromático", Proc. 38th ACM Symp. Theory of Computing , págs. 681–690, doi :10.1145/1132516.1132612, ISBN 1-59593-134-1, S2CID  5713815, ECCC  TR05-100.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Problema_de_las_camarillas&oldid=1247287775"