Cobertura de camarilla
En teoría de grafos , una cobertura de clique o partición en cliques de un grafo no dirigido dado es una colección de cliques que cubren todo el grafo. Una cobertura de clique mínima es una cobertura de clique que utiliza la menor cantidad posible de cliques. El k mínimo para el cual existe una cobertura de clique se denomina número de cobertura de clique del grafo dado.
Relación con la coloración
Una cobertura de clique de un grafo G puede verse como una coloración de grafo del grafo complementario de G , el grafo en el mismo conjunto de vértices que tiene aristas entre vértices no adyacentes de G . Al igual que las coberturas de clique, las coloraciones de grafo son particiones del conjunto de vértices, pero en subconjuntos sin adyacencias ( conjuntos independientes ) en lugar de cliques. Un subconjunto de vértices es un clique 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 cobertura de clique de G si y solo si es una coloración del complemento de G .
Complejidad computacional
El problema de cobertura de camarillas en la teoría de la complejidad computacional es el problema algorítmico de encontrar una cobertura de camarillas mínima, o (reformulado como un problema de decisión ) encontrar una cobertura de camarillas cuyo número de camarillas esté por debajo de un umbral dado. Encontrar una cobertura de camarillas mínima es NP-hard , y su versión de decisión es NP-complete . Fue uno de los 21 problemas originales de Richard Karp que se mostraron NP-completes en su artículo de 1972 "Reducibility Among Combinatorial Problems". [1]
La equivalencia entre las coberturas de camarillas y la coloración es una reducción que se puede utilizar para demostrar la NP-completitud del problema de la cobertura de camarillas a partir de la NP-completitud conocida de la coloración de gráficos. [2]
En clases especiales de gráficos
Los grafos perfectos se definen como grafos 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 del clique máximo . Según el teorema del grafo perfecto débil , el complemento de un grafo perfecto también es perfecto. Por lo tanto, los grafos perfectos también son los grafos en los que, para cada subgrafo inducido, el número de cobertura de clique es igual al tamaño del conjunto independiente máximo . Es posible calcular el número de cobertura de clique en grafos perfectos en tiempo polinomial .
Otra clase de grafos en los que se puede encontrar la cobertura mínima de clique en tiempo polinomial son los grafos sin triángulos . En estos grafos, cada cobertura de clique consiste en una coincidencia (un conjunto de pares disjuntos de vértices adyacentes) junto con conjuntos singleton para los vértices restantes no coincidentes. El número de cliques es igual al número de vértices menos el número de pares coincidentes. Por lo tanto, en grafos sin triángulos, la cobertura mínima de clique se puede encontrar utilizando un algoritmo para la coincidencia máxima .
La partición óptima en camarillas también se puede encontrar en tiempo polinomial para gráficos de ancho de camarilla acotado . [3] Estos incluyen, entre otros gráficos, los cografos y los gráficos hereditarios de distancia , que también son clases de gráficos perfectos.
El problema de la cobertura de camarilla sigue siendo NP-completo en algunas otras clases especiales de gráficos, incluidos los gráficos planos cúbicos [4] y los gráficos de disco unitario . [5]
Aproximación
La misma dureza de los resultados de aproximación que se conocen para la coloración de grafos también se aplica a la cobertura de clique. Por lo tanto, a menos que P = NP , no puede haber ningún algoritmo de aproximación de tiempo polinomial para ningún ε > 0 que, en grafos de n vértices, logre una relación de aproximación mejor que n 1 − ε . [6]
En los grafos donde cada vértice tiene como máximo tres vecinos , la cobertura de clique sigue siendo NP-dura, y hay una constante ρ > 1 tal que es NP-dura de aproximar con una razón de aproximación ρ o mejor. Sin embargo, en tiempo polinomial es posible encontrar una aproximación con una razón de 5/4. Es decir, este algoritmo de aproximación encuentra una cobertura de clique cuyo número de cliques no es más que 5/4 veces el óptimo. [4]
La técnica de Baker se puede utilizar para proporcionar un esquema de aproximación en tiempo polinomial para el problema en gráficos planares. [7]
Problemas relacionados
El problema relacionado de la cobertura de aristas de camarillas se refiere a la partición de las aristas de un grafo, en lugar de los vértices, en subgrafos inducidos por camarillas. También es NP-completo. [8]
Referencias
- ^ Karp, Richard (1972), "Reducibility Among Combinatorial Problems" (PDF) , en Miller, RE; Thatcher, JW (eds.), Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press, pp. 85–103, archivado desde el original (PDF) el 2011-06-29 , consultado el 2008-08-29
- ^ Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 0-7167-1045-5A1.2: GT19, pág.194.
- ^ Espelage, Wolfgang; Gurski, Frank; Wanke, Egon (2001), "Cómo resolver problemas de grafos NP-hard en grafos acotados por ancho de camarilla en tiempo polinomial", Taller internacional sobre conceptos de teoría de grafos en ciencias de la computación (WG 2001) , Lecture Notes in Computer Science, vol. 2204, Springer, págs. 117–128, doi :10.1007/3-540-45477-2_12, ISBN 978-3-540-42707-0.
- ^ ab Cerioli, MR; Faria, L.; Ferreira, TO; Martinhon, CAJ; Protti, F.; Reed, B. (junio de 2008), "Partición en camarillas para grafos cúbicos: caso planar, complejidad y aproximación", Discrete Applied Mathematics , 156 (12): 2270–2278, doi : 10.1016/j.dam.2007.10.015.
- ^ Dumitrescu, Adrián; Pach, János (2009), "Partición de camarilla mínima en gráficos de disco unitario", arXiv : 0909.1552 [cs.CG].
- ^ Zuckerman, D. (2007), "Extractores de grado lineal y la inaproximabilidad de Max Clique y el número cromático" (PDF) , Theory of Computing , 3 : 103–128, doi : 10.4086/toc.2007.v003a006.
- ^ Blanchette, Mathieu; Kim, Ethan; Vetta, Adrian (enero de 2012), "Cobertura de Clique en redes dispersas", Actas de 2012 del Decimocuarto Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX) , Sociedad de Matemáticas Industriales y Aplicadas, págs. 93-102, doi : 10.1137/1.9781611972924.10, ISBN 978-1-61197-212-2
- ^ Garey y Johnson (1979), Problema GT59.
