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.