### Abstract

The clique partitioning problem (CPP) can be formulated as follows: Given is a complete graph G = (V, E), with edge weights wij ∈ ℝ for all {i, j} ∈ E. A subset A ⊆ E is called a clique partition if there is a partition of V into nonempty, disjoint sets V1,…, Vk, such that each Vp (p = 1,…, k) induces a clique (i.e., a complete subgraph), and A = ∪math image {{i, j}|i, j ∈ Vp, i ≠ j}. The weight of such a clique partition A is defined as Σ{i,j}∈Awij. The problem is now to find a clique partition of maximum weight. The clique partitioning polytope P is the convex hull of the incidence vectors of all clique partitions of G. In this paper, we introduce several new classes of facet-defining inequalities of P. These suffice to characterize all facet-defining inequalities with right-hand side 1 or 2. Also, we present a procedure, called patching, which is able to construct new facets by making use of already-known facet-defining inequalities. A variant of this procedure is shown to run in polynomial time. Finally, we give limited empirical evidence that the facet-defining inequalities presented here can be of use in a cutting-plane approach for the clique partitioning problem.

Original language | English |
---|---|

Pages (from-to) | 209-226 |

Journal | Networks |

Volume | 38 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 2001 |

Externally published | Yes |

### Keywords

- polyhedral combinatorics
- clique partitioning
- facets

## Cite this

Oosten, M., Rutten, J. H. G. C., & Spieksma, F. C. R. (2001). The clique partitioning problem: Facets and patching facets.

*Networks*,*38*(4), 209-226. https://doi.org/10.1002/net.10004