Clique cover

In computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".

The clique cover problem (also sometimes called PARTITION INTO CLIQUES) is the problem of determining whether the vertices of a graph can be partitioned into "k" cliques. Given a partition of the vertices into "k" sets, it can be verified in polynomial time that each set forms a clique, so the problem is in NP. The NP-completeness of clique cover follows by reduction from GRAPH "k"-COLOURABILITY. To see this, first transform an instance "G" of GRAPH "k"-COLOURABILITY into its complement graph " G"'. A partition of " G' " into "k" cliques then corresponds to finding a partition of the vertices of "G" into "k" independent sets; each of these sets can then be assigned one colour to yield a "k"-colouring.

References

* Citation
first = Richard
last = Karp
authorlink = Richard Karp
contribution = Reducibility Among Combinatorial Problems
title = Proceedings of a Symposium on the Complexity of Computer Computations
editor-first = R. E.
editor-last = Miller
editor2-first = J. W.
editor2-last = Thatcher
publisher = Plenum Press
date = 1972
pages = 85-103
contribution-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
accessdate=2008-08-29
* A1.2: GT19, pg.194.