Problema de camarilla

Una camarilla maximal , a veces llamada inclusión-maximal, es una camarilla que no está incluida en una camarilla mayor. Por lo tanto, toda camarilla está contenida en una camarilla maximal. ^{[ 23 ]} Las camarillas maximales 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 contrario no se cumple. Hay algunos tipos de grafos en los que toda camarilla maximal es máxima; estos son los complementos de los grafos bien cubiertos , en los que todo conjunto independiente maximal es máximo. ^{[ 24 ]} Sin embargo, otros grafos tienen camarillas maximales que no son máximas.

Un único clique maximal puede ser encontrado por un algoritmo voraz directo . Comenzando con un clique arbitrario (por ejemplo, cualquier vértice individual o incluso el conjunto vacío), el clique actual crece un vértice a la vez recorriendo los vértices restantes del grafo. Para cada vértice v que este bucle examina, v agrega v al clique si es adyacente a cada vértice que ya está en el clique, y descarta v en caso contrario. Este algoritmo se ejecuta en tiempo lineal . ^{[ 25 ]} Debido a la facilidad para encontrar cliques maximales y su potencial tamaño pequeño, se ha prestado más atención al problema algorítmico mucho más difícil de encontrar un clique máximo o de otro modo grande. Sin embargo, algunas investigaciones en algoritmos paralelos han estudiado el problema de encontrar un clique maximal. En particular, se ha demostrado que el problema de encontrar el clique maximal lexicográficamente primero (el encontrado por el algoritmo anterior) es completo para la clase de funciones de tiempo polinomial . Este resultado implica que es improbable que el problema sea resoluble 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. Su tiempo es O ( n ^k k ² )  , expresado en notación O grande . Esto se debe a que hay O ( n ^k ) subgrafos que comprobar, cada uno de los cuales tiene O ( k ² ) aristas cuya presencia en G debe verificarse. Por lo tanto, el problema puede resolverse en tiempo polinomial cuando k es una constante fija. Sin embargo, cuando k no tiene un valor fijo, sino que puede variar como parte de la entrada del problema, el tiempo es exponencial. ^{[ 27 ]}

El caso no trivial más simple del problema de encontrar cliques 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 ajustado). El peor caso para esta fórmula ocurre cuando G es en sí mismo un clique. Por lo tanto, los algoritmos para listar 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 de grado más alto a 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 a todos los vecinos de v , busca a través de todas las aristas incidentes a un vecino de v, generando un triángulo para cada arista que tenga dos extremos marcados, y luego elimina las marcas y borra v del grafo. Como muestran los autores, el tiempo de este algoritmo es proporcional a la arboricidad del grafo (denotada a ( G ) ) multiplicada 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 un tiempo O ( m ^3/2 ) . De forma más general, todas las camarillas de k vértices pueden listarse 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 grafos de arboricidad constante, como los grafos planares (o en general grafos de cualquier familia de grafos cerrados menores 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 la garantía de que el grafo no contiene triángulos, existen algoritmos más rápidos. Como observan Itai y Rodeh (1978) , el grafo contiene un triángulo si y solo si su matriz de adyacencia y el cuadrado de la matriz de adyacencia contienen entradas no nulas en la misma celda. Por lo tanto, se pueden aplicar técnicas de multiplicación rápida de matrices para encontrar triángulos en tiempo O ( n².376 ) . Alon, Yuster y Zwick (1994) ^utilizaron la multiplicación rápida de matrices para mejorar el algoritmo O ( m³ ^/² ) para encontrar triángulos a O ( m¹.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 un resultado de Moon y Moser (1965) , todo grafo de n vértices tiene como máximo 3n ^{/3 cliques} maximales. Estos se pueden listar 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: un clique parcialmente construido (no maximal), un conjunto de vértices candidatos que podrían agregarse al clique y otro conjunto de vértices que no deben agregarse (porque hacerlo llevaría a un clique que ya se ha encontrado). El algoritmo intenta agregar los vértices candidatos uno por uno al clique 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 deben agregarse nuevamente. Se puede demostrar que las variantes de este algoritmo tienen un tiempo de ejecución en el peor de los casos de O ( ^{3n /3} ) , que coincide con el número de cliques que podrían necesitar listarse. ^{[ 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 su peor caso, otros algoritmos podrían ser preferibles. Como demostraron Tsukiyama et al. (1977) , también es posible listar todas las camarillas máximas en un grafo en un tiempo polinomial por camarilla generada. Un algoritmo como el suyo, en el que el tiempo de ejecución depende del tamaño de la salida, se conoce como algoritmo sensible a la salida . Su algoritmo se basa en las dos observaciones siguientes, que relacionan las camarillas máximas del grafo G dado 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 eliminando los no vecinos de v de K .

Utilizando estas observaciones, pueden generar todos los cliques maximales en G mediante 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 al agregar v a K y eliminar 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) proporcionan un algoritmo alternativo sensible a la salida basado en la multiplicación rápida de matrices. Johnson y Yannakakis (1988) muestran que incluso es posible listar todas las camarillas máximas en orden lexicográfico con retardo polinomial por camarilla. Sin embargo, la elección del orden es importante para la eficiencia de este algoritmo: para el orden inverso, no existe un algoritmo con 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 grafos en las que el número de camarillas está acotado polinomialmente. Estas familias incluyen grafos cordales , grafos completos , grafos sin triángulos , grafos de intervalos , grafos de boxicidad acotada y grafos planares . ^{[ 32 ]} En particular, los grafos planares tienen O ( n ) camarillas, de tamaño como máximo constante, que se pueden enumerar en tiempo lineal. Lo mismo es cierto para cualquier familia de grafos que sea a la vez dispersa (con 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 clique máxima, o el número de clique, de un grafo arbitrario de n vértices en tiempo O (3 ^{n /3} ) = O (1.4422 ⁿ ) utilizando uno de los algoritmos descritos anteriormente para listar todas las cliques máximas en el grafo y devolver la mayor. Sin embargo, para esta variante del problema de la clique, son posibles mejores límites de tiempo en el peor caso. El algoritmo de Tarjan y Trojanowski (1977) resuelve este problema en tiempo O (2 ^{n /3} ) = O (1.2599 ⁿ ) . 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 cliques encontradas dentro de la llamada serán subóptimas. Jian (1986) mejoró el tiempo a O (2 ^{0.304 n} ) = O (1.2346 ⁿ ) , y Robson (1986) lo mejoró a O (2 ^{0.276 n} ) = O (1.2108 ⁿ ) tiempo, a costa de un mayor uso de 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 la solución óptima se precalcula para todos los subgrafos pequeños conectados del grafo complemento . Estas soluciones parciales se utilizan para acortar la recursión de retroceso. El algoritmo más rápido conocido hoy es una versión refinada de este método por Robson (2001) que se ejecuta en tiempo O (2 ^{0.249 n} ) = O (1.1888 ⁿ ) . ^{[ 34 ]}

También se ha investigado ampliamente sobre algoritmos heurísticos para resolver problemas de clique máximo sin garantías de tiempo de ejecución en el peor caso, basados ​​en métodos que incluyen ramificación y acotación , ^{[ 35 ]} búsqueda local , ^{[ 36 ]} algoritmos voraces , ^{[ 37 ]} y programación con restricciones . ^{[ 38 ]} Las metodologías de computación no estándar que se han sugerido para encontrar cliques incluyen computación de ADN ^{[ 39 ]} y computación cuántica adiabática . ^{[ 40 ]} El problema del clique máximo fue objeto de un desafío de implementación patrocinado por DIMACS en 1992-1993, ^{[ 41 ]} y una colección de grafos 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 tratado anteriormente: poseen un número lineal de cliques maximales, de tamaño acotado, que pueden enumerarse en tiempo lineal. ^{[ 18 ]} En particular, para los grafos planares, cualquier clique 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 los 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 para encontrar cliques para muchas subclases de grafos perfectos. ^{[ 44 ]} En los grafos complemento de grafos bipartitos , el teorema de Kőnig permite resolver el problema del 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 puede describirse de forma equivalente como un problema de encontrar una camarilla máxima en un grafo de permutación. ^{[ 45 ]} Incluso, Pnueli y Lempel (1972) proporcionan un algoritmo alternativo de tiempo cuadrático para camarillas máximas en grafos de comparabilidad , una clase más amplia de grafos perfectos que incluye los grafos de permutación como un caso especial. ^{[ 46 ]} En los grafos cordales , las camarillas máximas pueden encontrarse enumerando los vértices en un orden de eliminación y comprobando los vecindarios de camarilla de cada vértice en este orden. ^{[ 47 ]}

En algunos casos, estos algoritmos también pueden extenderse a otras clases de grafos no perfectos. Por ejemplo, en un grafo circular , la vecindad 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 vecindad. ^{[ 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 vecindades compartidas 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 demás 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, puede encontrarse mediante una búsqueda por fuerza bruta en un tiempo esperado de 2 ^{O (log 2 n )} . Este es un límite de tiempo cuasipolinomial . ^{[ 50 ]} Aunque el número de camarillas de tales grafos suele ser muy cercano a 2  log ₂ n , los algoritmos voraces simples , así como las técnicas de aproximación aleatoria más sofisticadas, solo encuentran camarillas con un tamaño de log ₂ n , la mitad de grande. El número de camarillas máximas en tales grafos es con alta probabilidad exponencial en log ² n , lo que impide que los métodos que listan 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 grafos aleatorios que han sido aumentados 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 para detectar aquellas de tamaño o ( √ n ) (expresadas usando la notación de o pequeña ). ^{[ 55 ]}

Varios autores han considerado algoritmos de aproximación que intentan encontrar una camarilla o un conjunto independiente que, aunque no sea el máximo, tenga un tamaño lo más cercano posible al máximo en tiempo polinomial. Si bien 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 han realizado trabajos sobre 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 ) ² )    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 ³ n , cambiando a un algoritmo diferente de Boppana y Halldórsson (1992) para grafos con números de camarilla mayores, y eligiendo 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 ) ² /log ³ n )  del máximo. Aunque la razón de aproximación de este algoritmo es débil, es el mejor conocido hasta la fecha. ^{[ 57 ]} Los resultados sobre la dificultad de 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 lineal.

El problema de decisión de clique es NP-completo . Fue uno de los 21 problemas originales de Richard Karp que se demostró que eran 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 introdujo la teoría de los problemas NP-completos. ^{[ 60 ]} Debido a la dificultad del problema de decisión, el problema de encontrar un clique máximo también es NP-difícil. Si se pudiera resolver, también se podría resolver el problema de decisión, comparando el tamaño del clique máximo 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 muchos-uno del problema de satisfacibilidad booleana . Describe cómo traducir fórmulas booleanas en forma normal conjuntiva (FNC) a instancias equivalentes del problema de la máxima camarilla. ^{[ 61 ]} La satisfacibilidad, a su vez, fue demostrada como NP-completa en el teorema de Cook-Levin . A partir de una fórmula FNC 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 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 grafo 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 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 por fuerza bruta. ^{[ 62 ]} Sin embargo, es improbable que se pueda alcanzar un límite de tiempo subexponencial similar 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 su uso para demostrar varias cotas inferiores en la complejidad de circuitos . La existencia de una camarilla de un tamaño dado es una propiedad monótona de los grafos , lo que significa que, si una camarilla existe en un grafo dado, existirá en cualquier supergrafo . Debido a que esta propiedad es monótona, debe existir un circuito monótono, utilizando solo compuertas AND y OR , para resolver el problema de decisión de la 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 del 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 compuertas NOT , la complejidad sigue siendo superpolinómica. ^{[ 65 ]} Además, la profundidad de un circuito monótono para el problema de la camarilla que utiliza compuertas de fan-in acotado debe ser al menos un polinomio en el tamaño de la camarilla. ^{[ 66 ]}

La complejidad del árbol de decisión (determinista) para determinar una propiedad de un grafo es el número de preguntas del tipo "¿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 posee 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 se pueden formular. 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 en el peor de los casos) que un algoritmo aleatorio o cuántico necesita haber respondido para determinar correctamente si el grafo dado posee 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 de un árbol de decisión determinista para determinar cualquier propiedad no trivial de un grafo monótona es exactamente n ( n − 1)/2   . Para propiedades arbitrarias de grafos monótonas, esta conjetura permanece sin probar. 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 afirma que la complejidad del árbol de decisión aleatorio de funciones monótonas no triviales es Θ( n ² ) . La conjetura permanece sin probar, pero se ha resuelto para la propiedad de contener una k- clique para 2 ≤ k ≤ n . Se sabe que esta propiedad tiene una complejidad de árbol de decisión aleatorio Θ( n ² ) . ^{[ 69 ]} Para árboles de decisión cuánticos, la mejor cota inferior conocida 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 grafos. Se dice que un problema es tratable con parámetros fijos si existe un algoritmo para resolverlo con entradas de tamaño n y una función f , tal que el algoritmo se ejecuta en tiempo f ( k ) nO ⁽¹⁾  . Es decir, es tratable con parámetros fijos si se puede resolver en tiempo polinomial para cualquier valor fijo de k y, además ^, si el exponente del polinomio no depende de k . ^{[ 71 ]}

Para encontrar cliques de k vértices, el algoritmo de búsqueda por fuerza bruta tiene un tiempo de ejecución O( n ^k k ² ) . Debido a que el exponente de n depende de k , este algoritmo no es tratable con parámetros fijos. Aunque se puede mejorar mediante una multiplicación de matrices rápida , el tiempo de ejecución sigue teniendo un exponente que es lineal en k . Por lo tanto, aunque el tiempo de ejecución de los algoritmos conocidos para el problema de clique es polinomial para cualquier k fijo , estos algoritmos no son suficientes para la tratabilidad 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 tratables con parámetros fijos. Demostraron que el conjunto independiente (o, equivalentemente, clique) es difícil para el primer nivel de esta jerarquía, W[1] . Por lo tanto, según su conjetura, clique no tiene un algoritmo tratable con parámetros fijos. Además, este resultado proporciona la base para demostraciones de la 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 encontrar camarillas de k vértices no se puede hacer en 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 tratable con parámetros fijos. ^{[ 73 ]}

Aunque es improbable que los problemas de enumerar camarillas máximas o encontrar camarillas máximas sean tratables con parámetros fijos para el parámetro k , podrían serlo para otros parámetros de complejidad de instancia. Por ejemplo, se sabe que ambos problemas son tratables con parámetros fijos cuando se parametrizan por la degeneración del grafo de entrada. ^{[ 33 ]}

Desde hace 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 totalmente polinomial , 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 establecer conexiones entre la aproximación de las camarillas máximas y las pruebas verificables probabilísticamente . Utilizaron estas conexiones para demostrar la dificultad 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 ningún algoritmo de tiempo polinomial que aproxime la camarilla máxima a un factor mejor que O ( n ^{1 − ε}   ) , a menos que P = NP . ^{[ 75 ]}

La idea general de estos resultados de inaproximabilidad es formar un grafo que represente un sistema de prueba verificable probabilísticamente para un problema NP-completo, como el problema de satisfacibilidad booleana. En un sistema de prueba verificable probabilísticamente, una prueba se representa como una secuencia de bits. Una instancia del problema de satisfacibilidad debe tener una prueba válida si y solo si es satisfacible. La prueba se verifica mediante un algoritmo que, tras un cálculo en tiempo polinomial sobre la entrada del problema de satisfacibilidad, elige examinar un pequeño número de posiciones seleccionadas aleatoriamente de la cadena de prueba. Dependiendo de los valores encontrados en esa muestra de bits, el verificador aceptará o rechazará la prueba, sin examinar el resto de los bits. No se permiten falsos negativos: una prueba válida siempre debe ser aceptada. Sin embargo, una prueba inválida puede aceptarse erróneamente en ocasiones. 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 verificable de este tipo en un problema de clique, se forma un grafo con un vértice por 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 esas posiciones que harían que el verificador aceptara la prueba. Se puede representar mediante una palabra parcial con un 0 o un 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 bits en cada posición que ambas examinan. Cada cadena de prueba (válida o inválida) corresponde a un clique, el conjunto de ejecuciones de aceptación que ven esa cadena de prueba, y todos los cliques máximos surgen de esta manera. Uno de estos cliques 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, aceptada por todas las ejecuciones del verificador, y esta cadena corresponderá a una gran camarilla 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 un pequeño número de ejecuciones del verificador que la aceptan erróneamente, y todas las camarillas son pequeñas. Por lo tanto, si se pudiera distinguir en tiempo polinomial entre grafos con grandes camarillas y grafos con pequeñas camarillas, o si se pudiera aproximar con precisión el problema de las camarillas, entonces aplicar esta aproximación a los grafos generados a partir de instancias de satisfacibilidad permitiría distinguir las instancias satisfacibles de las insatisfacibles. Sin embargo, esto no es posible a menos que P  =  NP. ^{[ 76 ]}