En informática , el problema de 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 dependiendo de qué camarillas y qué información sobre las camarillas se debe encontrar. Las formulaciones comunes del problema de 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 una camarilla mayor que un tamaño determinado.
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 el conocimiento mutuo. Entonces, una camarilla representa un subconjunto de personas que se conocen entre sí, y se pueden utilizar algoritmos para encontrar camarillas para descubrir estos grupos de amigos mutuos. Además de 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 las camarillas son difíciles. El problema de decisión de camarilla es NP-completo (uno de los 21 problemas NP-completos de Karp ). El problema de encontrar la camarilla máxima es intratable en términos de parámetros fijos y difícil de aproximar . Y enumerar todas las camarillas máximas puede requerir un tiempo exponencial, ya que existen gráficos con muchas camarillas máximas exponencialmente. Por tanto, gran parte de la teoría sobre el problema de la camarilla se dedica 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 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á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 todas las camarillas máximas en el peor de los casos, y también es posible enumerarlas en tiempo polinomial por camarilla.
El estudio de subgrafos completos en matemáticas es anterior a la terminología de "camarilla". Por ejemplo, los subgrafos completos aparecen tempranamente en la literatura matemática en la reformulación teórica de grafos de la teoría de Ramsey por Erdős y Szekeres (1935). Pero el término "camarilla" y el problema de enumerar 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 de las ciencias sociales también han definido varios otros tipos de camarillas y camarillas máximas en las redes sociales, "subgrupos cohesivos" de personas o actores en la red, todos los cuales comparten uno de varios tipos diferentes de relación de conectividad. Muchas de estas nociones generalizadas de camarillas también se pueden encontrar construyendo un gráfico no dirigido cuyos bordes representen pares relacionados de actores de la red social y luego aplicando un algoritmo para el problema de camarilla 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 sus 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, a partir del trabajo de Cook (1971) y Karp (1972), los investigadores comenzaron a utilizar la teoría de la completitud NP 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 de artículos innovadores que comenzaron con Feige et al. (1991) demostraron 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 [3] y para modelar el acoplamiento molecular y los sitios de unión de 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 sean aproximadamente iguales, dentro de una tolerancia determinada. Una camarilla en este gráfico representa un conjunto de pares de átomos coincidentes en los 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 pruebas. [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 de hipercubos cara a cara 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]
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 . Una camarilla en un gráfico 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 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 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]
Los primeros cuatro de estos problemas son todos importantes en aplicaciones prácticas. El problema de la decisión de camarilla no tiene importancia práctica; se formula de esta manera para aplicar la teoría de la completitud NP a problemas de búsqueda de camarillas. [19]
El problema de la camarilla y el problema del conjunto independiente son complementarios: una camarilla en G es un conjunto independiente en el gráfico complementario de G y viceversa. [20] Por lo tanto, muchos resultados computacionales pueden aplicarse igualmente bien a cualquiera de los problemas, 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 se puede resolver en tiempo polinómico para gráficos planos [21], mientras que el problema de conjuntos independientes sigue siendo NP-duro en gráficos planos. [22]
Una camarilla máxima , a veces llamada inclusión máxima, es una camarilla que no está incluida en una camarilla más grande. Por lo tanto, cada camarilla está contenida en una camarilla máxima. [23] 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. [24] Sin embargo, otros gráficos tienen camarillas máximas que no son máximas.
Se puede encontrar una única camarilla máxima mediante un sencillo algoritmo codicioso . Comenzando con una camarilla arbitraria (por ejemplo, cualquier vértice único o incluso el conjunto vacío), haga crecer la camarilla actual un vértice a la vez recorriendo los vértices restantes del gráfico. Para cada vértice v que examina este bucle, agregue v a la camarilla si 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 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áfica (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 pueda resolverse dentro de la clase de complejidad paralela NC . [26]
Se puede probar si un gráfico G contiene una camarilla de k -vértices y encontrar la 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 O ( n k ) subgrafos para verificar, cada uno de los cuales tiene O ( k 2 ) aristas 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. [27]
El caso no trivial más simple del problema de búsqueda de camarillas es encontrar un triángulo en un gráfico o, de manera equivalente, determinar si el gráfico está libre de triángulos . En un gráfico G con m aristas, puede haber como máximo Θ ( m 3/2 ) triángulos (usando notación theta grande para indicar que este límite es ajustado). 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 ) de tiempo en el peor de los casos (usando 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 de mayor a menor grado 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. vértice en la lista. Para hacerlo, el algoritmo marca todos los vecinos de v , busca en todos los bordes incidentes con un vecino de v generando un triángulo para cada borde que tiene dos puntos finales marcados, y luego elimina las marcas y elimina v del gráfico. Como muestran los autores, el tiempo para este algoritmo es proporcional a la arboricidad del gráfico (denotado como ( G ) ) multiplicado por el número de aristas, que es O ( m a ( G )) . 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 elevada a la potencia ( k − 2) . Para gráficos de arboricidad constante, como gráficos planos (o en gráficos generales de cualquier familia de gráficos cerrados menores no triviales ), este algoritmo toma tiempo O ( m ) , que es óptimo ya que es lineal en el tamaño de la entrada. [18]
Si uno desea un solo triángulo, o la seguridad de que el gráfico no tiene triángulos, son posibles algoritmos más rápidos. Como observan Itai y Rodeh (1978), la gráfica contiene un triángulo si y sólo si su matriz de adyacencia y el cuadrado de la matriz de adyacencia contienen entradas distintas de cero en la misma celda. Por lo tanto, se pueden aplicar técnicas rápidas de multiplicación de matrices para encontrar triángulos en el tiempo O ( n 2,376 ) . Alon, Yuster y Zwick (1994) utilizaron la multiplicación rápida de matrices 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 mayores de k . [29]
Según 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 recursivo de retroceso 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 llevaría a a una camarilla que ya ha sido encontrada). El algoritmo intenta agregar los vértices candidatos uno por uno a la camarilla parcial, realizando 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 ) , que coincide con el número de camarillas que podrían necesitar enumerarse. [30] 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. [31]
Sin embargo, cuando el número de camarillas es significativamente menor que en el peor de los casos, podrían ser preferibles otros algoritmos. Como Tsukiyama et al. (1977), también es posible enumerar todas las camarillas máximas en un gráfico en una cantidad de tiempo que es polinómica por camarilla generada. Un algoritmo como el suyo en el que el tiempo de ejecución depende del tamaño de salida se conoce como algoritmo sensible a la salida . Su algoritmo se basa en las dos observaciones siguientes, que relacionan los grupos máximos del gráfico G dado con los grupos máximos de un gráfico G \ v formado eliminando un vértice arbitrario v de G :
Usando estas observaciones, pueden generar todas las camarillas máximas en G mediante un algoritmo recursivo que elige un vértice v arbitrariamente y luego, para cada camarilla máxima K en G \ v , genera tanto K como la camarilla formada sumando v a K y eliminando los no -vecinos de v . Sin embargo, algunas camarillas de G pueden generarse de esta manera a partir de más de una camarilla principal de G \ v , por lo que eliminan duplicados generando una camarilla en G solo cuando su padre en G \ v es lexicográficamente máximo entre todas las camarillas principales 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 una rápida multiplicación de matrices. Johnson y Yannakakis (1988) muestran que incluso es posible enumerar todos los grupos máximos en orden lexicográfico con un retraso polinómico 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 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áficas cordales , gráficas completas , gráficas sin triángulos , gráficas de intervalo , gráficas de boxicidad acotada y gráficas planas . [32] En particular, los gráficos planos tienen camarillas O ( n ) , de tamaño constante como máximo, que pueden enumerarse en tiempo lineal. Lo mismo es cierto para cualquier familia de gráficos que sea dispersa (que tenga un número de aristas como máximo constante multiplicado por el número de vértices) y cerrado bajo la operación de tomar subgrafos. [18] [33]
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 devolver 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 & Trojanowski (1977) resuelve este problema en el tiempo O (2 n /3 ) = O (1,2599 n ) . Es un esquema de retroceso recursivo similar al del algoritmo Bron-Kerbosch , pero es capaz de eliminar algunas llamadas recursivas cuando se puede demostrar que las camarillas encontradas dentro de la llamada no serán ó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 casos 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 pequeños subgrafos conectados del gráfico complementario . Estas soluciones parciales se utilizan para atajar la recursividad 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 el tiempo O (2 0,249 n ) = O (1,1888 n ) . [34]
También se ha realizado una extensa investigación sobre algoritmos heurísticos para resolver problemas de camarilla máxima sin garantías de tiempo de ejecución en el peor de los casos, basados en métodos que incluyen ramificación y límite , [35] búsqueda local , [36] algoritmos codiciosos , [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 del 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]
Los gráficos planos y otras familias de gráficos dispersos se han analizado anteriormente: tienen linealmente muchas camarillas máximas, de tamaño acotado, que se pueden enumerar en tiempo lineal. [18] En particular, para gráficos planos, 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 camarilla es igual a su número cromático , y que esta igualdad también se cumple en cada uno de sus subgrafos inducidos . Para gráficas perfectas, es posible encontrar una camarilla máxima en tiempo polinómico, 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 camarillas para muchas subclases de gráficos perfectos. [44] En los gráficos de complemento de los gráficos bipartitos , el teorema de Kőnig permite resolver el problema de camarilla máxima utilizando técnicas de emparejamiento . 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. Por el contrario, 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. [45] Incluso, Pnueli y Lempel (1972) proporcionan un algoritmo alternativo de tiempo cuadrático 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 las vecindades de camarilla de cada vértice en este orden. [47]
En algunos casos, estos algoritmos también se pueden extender a otras clases de gráficos no perfectos. Por ejemplo, en un gráfico circular , la vecindad de cada vértice es un gráfico de permutación, por lo que se puede encontrar una camarilla máxima en un gráfico circular aplicando el algoritmo del gráfico de permutación a cada vecindad. [48] De manera similar, en un gráfico 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 gráficos bipartitos a vecindades compartidas de pares de vértices. [49]
Karp (1976) sugirió 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 una probabilidad de 1/2 , independientemente de los otros bordes). 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 polinómico . [50] Aunque el número de camarilla 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 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 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. [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 agregando 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 polinómico para detectar aquellas de tamaño o ( √ n ) (expresadas usando poco- o notación ). [55]
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 tan cercano al máximo como se puede encontrar en 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 camarilla complementaria, también se ha trabajado en algoritmos de aproximación que no utilizan tales supuestos de dispersión. [56]
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 . Al usar 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 , cambiar a un algoritmo diferente de Boppana y Halldórsson (1992) para gráficos con números de camarilla más altos y elegir un algoritmo de dos camarilla de vértices si ambos algoritmos no logran encontrar 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 el ratio 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.
El problema de decisión de camarilla es NP-completo . Fue uno de los 21 problemas originales de Richard Karp que se mostró NP-completo 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 los problemas NP-completos. [60] Debido a la dureza del problema de decisión, el problema de encontrar una camarilla máxima también es NP-difícil. Si se pudiera resolverlo, también se 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 normal conjuntiva (CNF) a instancias equivalentes del problema de camarilla máxima. [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 gráfico 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 de 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 sean negaciones de cada uno. Si k denota el número de cláusulas en la fórmula CNF, entonces las k camarillas de 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 satisfactoria si y sólo si existe una camarilla de k -vértices. [59]
Algunos problemas NP-completos (como el problema del viajante en gráficos planos ) 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 tal límite de tiempo subexponencial sea posible para el problema de camarilla en gráficos arbitrarios, ya que implicaría límites subexponenciales similares para muchos otros problemas estándar NP-completos. [63]
La dificultad computacional del problema de la camarilla ha llevado a que se utilice para demostrar varios límites inferiores en la complejidad del circuito . La existencia de una camarilla de un tamaño determinado es una propiedad del gráfico monótono , lo que significa que, si existe una camarilla en un gráfico determinado, existirá en cualquier supergrafo . Debido a que esta propiedad es monótona, debe existir un circuito monótono, que utilice únicamente puertas y o puertas , para resolver el problema de decisión de camarilla para un tamaño de camarilla fijo determinado. 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 superpolinomial. [65] Además, la profundidad de un circuito monótono para el problema de la camarilla que utiliza puertas de entrada en abanico acotada debe ser al menos un polinomio en el tamaño de la camarilla. [66]
La complejidad (determinista) del árbol de decisión para determinar una propiedad gráfica 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 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 posibles preguntas que formular. Por lo tanto, cualquier propiedad gráfica se puede determinar con como máximo 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 el peor de los casos) que un algoritmo aleatorio o cuántico debe haber respondido para determinar correctamente si el gráfico 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 determinista del árbol de decisión para determinar cualquier propiedad gráfica monótona no trivial es exactamente n ( n − 1)/2 . Para propiedades arbitrarias de gráficos monótonos, esta conjetura aún no ha sido probada. 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 -clique 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 sigue sin ser probada, pero se ha resuelto para la propiedad de contener una k camarilla 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á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 . [70]
La complejidad parametrizada es el estudio teórico de la complejidad de problemas que están naturalmente equipados con un parámetro 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 gráficos. 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 ejecute en el tiempo f ( k ) n O (1) . Es decir, es manejable con parámetros fijos si se puede resolver en tiempo polinómico 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 todavía tiene un exponente lineal en k . Por lo tanto, aunque el tiempo de ejecución de los algoritmos conocidos para el problema de la camarilla es polinómico para cualquier k fijo , estos algoritmos no son suficientes para la manejabilidad de parámetros fijos. Downey y Fellows (1995) definieron una jerarquía de problemas parametrizados, la jerarquía W, que, según conjeturaron, no tenía algoritmos manejables de parámetros fijos. Demostraron que el conjunto independiente (o, equivalentemente, la camarilla) es difícil para el primer nivel de esta jerarquía, W[1] . Por tanto, según 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 tanto, sirve como análogo del teorema de Cook-Levin para la complejidad parametrizada. [72]
Chen et al. (2006) demostraron que no se pueden encontrar k camarillas de 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. [73]
Aunque es poco probable que los problemas de enumerar camarillas máximas o 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 están parametrizados por la degeneración del gráfico de entrada. [33]
Desde hace mucho tiempo 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 en tiempo totalmente polinomial , a menos que P = NP. 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 hacer conexiones entre la aproximación de camarillas máximas y las pruebas comprobables probabilísticamente . Utilizaron estas conexiones para demostrar la dureza de los resultados de aproximación para el problema de 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 polinómico que aproxima la camarilla máxima dentro de un factor mejor que O ( n 1 − ε ) , a menos que P = NP . [75]
La idea aproximada de estos resultados de inaproximabilidad es formar un gráfico que represente un sistema de prueba comprobable probabilísticamente 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. Un ejemplo del problema de satisfacibilidad debería tener una prueba válida si y sólo si es satisfacible. La prueba se verifica mediante un algoritmo que, después de un cálculo en tiempo polinómico en la entrada del 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. Por cada prueba inválida, la probabilidad de que el verificador la acepte debe ser baja. [76]
Para transformar un sistema de prueba comprobable probabilísticamente 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 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 bits para aquellas posiciones que harían que el verificador aceptara la prueba. Puede representarse mediante una palabra parcial con un 0 o 1 en cada posición examinada y un carácter comodín en cada posición restante. En este gráfico, dos vértices son adyacentes si las dos ejecuciones de aceptación correspondientes ven los mismos valores de bits en cada posición que ambos examinan. Cada cadena de prueba (válida o no válida) 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 sólo si corresponde a una cadena de prueba que muchos verificadores de pruebas 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 camarilla 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 ejecuciones de verificación que la aceptan por error y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en tiempo polinómico entre gráficos que tienen camarillas grandes y gráficos en los que todas las camarillas son pequeñas, o si se pudiera aproximar con precisión el problema de camarillas, entonces aplicar esta aproximación a las gráficas generadas a partir de instancias de satisfacibilidad permitiría que las instancias satisfactibles distinguirse de los casos insatisfactorios. Sin embargo, esto no es posible a menos que P = NP. [76]
{{citation}}: Mantenimiento CS1: posdata ( enlace ).