En la teoría de grafos , una cubierta de camarilla o una divisió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 cubierta de camarilla mínima es una cubierta de camarilla que usa la menor cantidad posible de camarillas. El k mínimo para el que existe una cobertura de clique se denomina número de cobertura de clique del gráfico dado.
Relación con la coloración
Una cubierta clique de un gráfico de G puede ser visto como un gráfico de la coloración de la gráfica complemento 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 camarillas, los colores de los gráficos son particiones del conjunto de vértices, pero en subconjuntos sin adyacencias ( conjuntos independientes ) en lugar de camarillas. 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 de camarilla de G si y solo si es una coloración del complemento de G .
Complejidad computacional
El problema de la cobertura de la camarilla en la teoría de la complejidad computacional es el problema algorítmico de encontrar una cobertura mínima de la camarilla, o (parafraseado como un problema de decisión ) encontrar una cubierta de la camarilla cuyo número de camarillas esté por debajo de un umbral dado. Encontrar una cobertura mínima de camarilla 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 cubierta de clique a partir de la completitud NP conocida de la coloración de gráficos. [2]
En clases especiales de gráficos
Los gráficos perfectos se definen como los 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 gráfico perfecto débil , el complemento de un gráfico perfecto también es perfecto. Por lo tanto, los gráficos perfectos son también los gráficos en los que, para cada subgráfico inducido, el número de cobertura de la camarilla 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 la cobertura mínima de la camarilla se puede encontrar en el tiempo polinomial son los gráficos sin triángulos . En estos gráficos, cada cobertura de camarilla consiste en una coincidencia (un conjunto de pares disjuntos de vértices adyacentes) junto con conjuntos de singleton para los vértices no emparejados restantes. El número de camarillas es igual al número de vértices menos el número de pares emparejados. Por lo tanto, en los gráficos sin triángulos, la cobertura mínima de la camarilla se puede encontrar utilizando un algoritmo para la máxima coincidencia .
La partición óptima en camarillas también se puede encontrar en el tiempo polinomial para gráficos de ancho de camarilla acotado . [3] Estos incluyen, entre otros gráficos, los gráficos cográficos y los gráficos hereditarios de distancia , que también son clases de gráficos perfectos.
Aproximación
La misma dureza de los resultados de aproximación que se conocen para colorear gráficos también se aplica a la cobertura de clique. Por lo tanto, a menos que P = NP , no puede haber un algoritmo de aproximación de tiempo polinómico para cualquier ε > 0 que, en gráficos de n -vértices, logre una relación de aproximación mejor que n 1 - ε . [4]
En los gráficos donde cada vértice tiene como máximo tres vecinos , la cobertura de la camarilla permanece NP-hard, y hay una constante ρ > 1 tal que es NP-hard aproximar con una relación de aproximación ρ o mejor. Sin embargo, en tiempo polinomial es posible encontrar una aproximación con razón 5/4. Es decir, este algoritmo de aproximación encuentra una cobertura de camarillas cuyo número de camarillas no es más de 5/4 veces el óptimo. [5]
Problemas relacionados
El problema relacionado con la cobertura de bordes de camarillas se refiere a dividir los bordes de un gráfico, en lugar de los vértices, en subgrafos inducidos por camarillas. También es NP-completo. [6]
Referencias
- ^ Karp, Richard (1972), "Reducibilidad entre problemas combinatorios" (PDF) , en Miller, RE; Thatcher, JW (eds.), Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press, págs. 85-103 , consultado el 29 de agosto de 2008
- ^ Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , WH Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pág.194.
- ^ Espelage, Wolfgang; Gurski, Frank; Wanke, Egon (2001), "Cómo resolver problemas de gráficos NP-duros en gráficos acotados de ancho de camarilla en tiempo polinomial", Taller internacional sobre conceptos teóricos de gráficos en ciencias de la computación (WG 2001) , Lecture Notes in Computer Science, 2204 , Springer, págs. 117-128, doi : 10.1007 / 3-540-45477-2_12.
- ^ Zuckerman, D. (2007), "Extractores de grados lineales y la falta de aproximación de Max Clique y Chromatic Number" (PDF) , Teoría de la Computación , 3 : 103-128, doi : 10.4086 / toc.2007.v003a006.
- ^ Cerioli, MR; Faria, L .; Ferreira, TO; Martinhon, CAJ; Protti, F .; Reed, B. (junio de 2008), "Partición en camarillas para gráficas cúbicas: caso plano, complejidad y aproximación", Matemáticas aplicadas discretas , 156 (12): 2270–2278, doi : 10.1016 / j.dam.2007.10.015.
- ^ Garey y Johnson (1979) , Problema GT59.