En la teoría de grafos , una cubierta de camarilla o partición en camarillas de un gráfico no dirigido dado es una partición de los vértices del gráfico en camarillas , subconjuntos de vértices dentro de los cuales cada dos vértices son adyacentes. Una cobertura de camarilla mínima es una cobertura de camarilla que utiliza la menor cantidad de camarillas posible. El k mínimo para el que existe una cobertura de camarilla se denomina número de cobertura de camarilla del gráfico dado.
Una cubierta clique de un gráfico G puede verse como un gráfico coloreado del gráfico complementario de G , el gráfico en el mismo conjunto de vértices que tiene bordes entre vértices no adyacentes de G . Al igual que las cubiertas de clicas, los colores de gráficos son particiones del conjunto de vértices, pero en subconjuntos sin adyacencias ( conjuntos independientes ) en lugar de cliclas. Un subconjunto de vértices es una camarilla en G si y solo si es un conjunto independiente en el complemento de G , por lo que una partición de los vértices de G es una cubierta camarilla de G si y solo si es una coloración del complemento de g _
El problema de cobertura de camarilla en la teoría de la complejidad computacional es el problema algorítmico de encontrar una cobertura de camarilla mínima o (reformulado como un problema de decisión ) encontrar una cobertura de camarilla cuyo número de camarillas esté por debajo de un umbral dado. Encontrar una cobertura de camarilla mínima es NP-difícil , y su versión de decisión es NP-completa . Fue uno de los 21 problemas originales de Richard Karp que se muestra NP-completo en su artículo de 1972 "Reducibilidad entre problemas combinatorios". [1]
La equivalencia entre las cubiertas de clique y la coloración es una reducción que se puede utilizar para probar la completitud NP del problema de la cubierta de clique a partir de la completitud NP conocida de la coloración de gráficos. [2]
Los gráficos perfectos se definen como aquellos gráficos en los que, para cada subgrafo inducido , el número cromático (número mínimo de colores en una coloración) es igual al tamaño de la camarilla máxima . Según el teorema del grafo perfecto débil , el complemento de un grafo perfecto también es perfecto. Por tanto, los grafos perfectos son también aquellos en los que, para cada subgrafo inducido, el número de cobertura de clique es igual al tamaño del conjunto máximo independiente . Es posible calcular el número de cobertura de la camarilla en gráficos perfectos en tiempo polinomial .
Otra clase de gráficos en los que se puede encontrar la cobertura de camarilla mínima en tiempo polinomial son los gráficos sin triángulos . En estos gráficos, cada cobertura de camarilla consta de una coincidencia (un conjunto de pares disjuntos de vértices adyacentes) junto con conjuntos únicos para los vértices restantes no coincidentes. El número de camarillas es igual al número de vértices menos el número de pares coincidentes. Por lo tanto, en gráficos sin triángulos, la cobertura de camarilla mínima se puede encontrar utilizando un algoritmo para la coincidencia máxima .