Cobertura clique

Em complexidade computacional, encontrar uma cobertura de clique miníma é um problema NP-completo relacionado à Teoria dos grafos. Este problema foi um dos 21 problemas originais de Karp mostrados serem NP-completos em seu artigo de 1972 "Reducibility Among Combinatorial Problems" (Redutibilidade entre problemas combinatórios).

O Problema da cobertura de clique (também chamado as vezes de partição em cliques) é o problema de se determinar se os vértices de um grafo podem ser particionados em k cliques. Dada uma partição dos vertices em k conjuntos, pode ser verificado em [tempo polinomial] que cada conjunto forma um clique, então o problema está em NP. A NP-completude de uma cobertura clique segue de uma redução da k-Colorabilidade de um grafo. Para ver tal redução, primeiros transformamos uma instância G de um k-colorabilidade Grafo em seu Grafo complementar G'. Uma partição de G' em k cliques então corresponde a encontrar uma partição dos vertices de G em k Conjuntos independentes; a cada um desses conjuntos pode então ser atribuída uma cor para ser produzida uma k-coloração.

O problema relacionado cobertura de arestas de clique considera conjuntos de cliques que incluem todas as arestas de um dado caminho. Ele também é NP-completo.

Referências

• Karp, Richard (1972), «Reducibility Among Combinatorial Problems» (PDF), in: Miller, R. E.; Thatcher, J. W., Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, pp. 85–103, consultado em 29 de agosto de 2008 
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5  A1.2: GT19, pg.194.