Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).