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.
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.