MINIMUM CLIQUE PARTITION

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A clique partition for G, i.e., a partition of V into disjoint subsets $V_1,V_2,\ldots,V_k$ such that, for $1\le i\le k$, the subgraph induced by $V_i$ is a complete graph.
• MEASURE: Cardinality of the clique partition, i.e., the number of disjoint subsets $V_i$.

  
  

• Good News: Equivalent to MINIMUM GRAPH COLORING [396]. See results theirein.
• Garey and Johnson: GT15