A subset A of the edge set of a graph is called a clique partitioning of G if there is a partition of the node set V into disjoint sets such that each induces a clique, i.e., a complete (but not necessarily maximal) subgraph of G, and such that . Given weights for all , the clique partitioning problem is to find a clique partitioning A of G such that is as small as possible. This problem - known to be
