- INSTANCE: Graph .
- SOLUTION:
A clique cover for
*G*, i.e., a collection of subsets of*V*, such that each induces a complete subgraph of*G*and such that for each edge there is some that contains both*u*and*v*. - MEASURE:
Cardinality of the clique cover, i.e., the number of subsets .

*Good News:*Approximable within if MINIMUM CLIQUE PARTITION is approximable within [221].*Bad News:*Not approximable within unless MINIMUM CLIQUE PARTITION is approximable within .*Comment:*Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction [338] and [444]. The constrained variation in which the input is extended with a positive integer*k*, a vertex and a subset*S*of*V*, and the problem is to find the clique cover of size*k*that contains the largest number of vertices from*S*, is not approximable within for some [476].*Garey and Johnson:*GT17