Problema de la cobertura de cliques
En teoría de la complejidad computacional, el problema de la cobertura de cliques es un problema de decisión NP-completo de la teoría de grafos. Es uno de los 21 problemas originales que Richard Karp demostró que era NP-completo en su artículo de 1972 «Reducibility Among Combinatorial Problems».
El problema consiste en determinar si los vértices de un grafo pueden ser particionados en k cliques. Dada una partición de los vértices en k conjuntos, se puede verificar en tiempo polinómico que cada conjunto forma un clique, de modo que el problema es NP. La NP-completitud se puede demostrar por reducción polinómica a partir del problema de k-coloración de grafos. Para ver esto, basta se transforma una instancia G en el grafo complemento G' . Así, encontrar una partición de G' en k cliques corresponde a encontrar una partición de vértices de G en k conjuntos independientes; a cada uno de estos conjuntos se le puede asignar uno de los k colores.
El problema relacionado de cobertura de aristas de cliques, que considera conjuntos de cliques que incluyen todas las aristas de un grafo dado, también es NP-completo.
Véase también editar
Referencias editar
- Karp, Richard (1972), Miller, R. E.; Thatcher, J. W., eds., Reducibility Among Combinatorial Problems, Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, pp. 85-103, archivado desde el original el 29 de diciembre de 2013, consultado el 26 de diciembre de 2013..
- Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.
Datos: Q16622193
