Facets of the clique partitioning polytope (Q752015)

The clique partitioning problem in an edge weighted graph (with negative weights in general) is that of finding a partition of its vertices into blocks such that the sum of the weights on all edges that are within blocks is minimized. This problem is NP complete. In this paper various facets of the polytope of clique partitions are described. This endeavor is potentially useful for actually solving examples of such problems if these facets turn out to be the ones relevant at the solution point. Facets are obtained corresponding to 2-partitions, 2-chorded cycles, paths and wheels. Triangle inequality constraints and 2-partition inequalities are said to be often enough for utility in examples.