GT13 M INIMUM C LIQUE P ARTITION

       
• I NSTANCE : Graph .
• S OLUTION : A clique partition for G , i.e., a partition of V into disjoint subsets such that, for , the subgraph induced by is a complete graph.
• M EASURE : Cardinality of the clique partition, i.e., the number of disjoint subsets .

• Good News: Approximable within [ 148 ].
• Bad News: Not approximable within for some [ 264 ].
• Comment: Equivalent to M INIMUM G RAPH C OLORING [ 287 ]. The complementary maximization problem, where |V|-k , is to be maximized, is approximable within 4/3 [ 153 ].
• Garey and Johnson: GT15