FACETS OF THE CLIQUE PARTITIONING POLYTOPE

A subset A of the edge set of a graph G = (V, E) is called a clique partitioning of G is there is a partition of the node set V into disjoint sets W1,⋯, Wk such that each Wi induces a clique, i.e., a complete (but not necessarily maximal) subgraph of G, and such that A = ∪i=1k1{uv|u, v ∈ Wi, u ≠ v}. Given weights we∈ℝ for all e ∈ E, the clique partitioning problem is to find a clique partitioning A of G such that ∑e∈Awe is as small as possible. This problem-known to be[Figure not available: see fulltext.]-hard, see Wakabayashi (1986)-comes up, for instance, in data analysis, and here, the underlying graph G is typically a complete graph. In this paper we study the clique partitioning polytope[Figure not available: see fulltext.] of the complete graph Kn, i.e.,[Figure not available: see fulltext.] is the convex hull of the incidence vectors of the clique partitionings of Kn. We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs of Kn induce facets of[Figure not available: see fulltext.]. 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). © 1990 The Mathematical Programming Society, Inc.