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^k1{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 _eAw_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).