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.
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]
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]
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]
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]
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 luego elimina las marcas y borra v del grafo. Como muestran los autores, el tiempo para este algoritmo es proporcional a la arboricidad del grafo (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 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 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 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 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]
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í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 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 :
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 como salida 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 .
En base a este resultado, es posible listar 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 listarse 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]
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]
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]
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]
Varios autores han considerado algoritmos de aproximación que intentan encontrar un grupo 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 del grupo complementario, 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.
El problema de decisión de la 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 las negaciones del otro. 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]
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]
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 grafos monótonos arbitrarios, 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]
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]
Resultados débiles que sugieren que el problema de la camarilla podría ser difícil de aproximar se conocen desde hace mucho tiempo. Garey y Johnson (1978) observaron que, debido 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 estuviera disponible una aproximación demasiado precisa, redondear su valor a un entero daría el número de camarilla exacto. Sin embargo, poco más se sabía 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 . Usaron 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]
{{citation}}: Mantenimiento de CS1: postscript ( enlace ).