Premium
The clique partitioning problem: Facets and patching facets
Author(s) -
Oosten Maarten,
Rutten Jeroen H. G. C.,
Spieksma Frits C. R.
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10004
Subject(s) - combinatorics , partition (number theory) , mathematics , polytope , clique , convex hull , clique graph , facet (psychology) , polyhedral combinatorics , disjoint sets , clique percolation method , discrete mathematics , graph , regular polygon , convex optimization , convex set , line graph , geometry , psychology , social psychology , personality , big five personality traits , voltage graph , complex network
The clique partitioning problem (CPP) can be formulated as follows: Given is a complete graph G = ( V, E ), with edge weights w ij ∈ ℝ 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 V 1 ,…, V k , such that each V p ( p = 1,…, k ) induces a clique (i.e., a complete subgraph), and A = ∪ p =1 k{{ i, j }| i, j ∈ V p , i ≠ j }. The weight of such a clique partition A is defined as Σ { i,j }∈ A w ij . 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. © 2001 John Wiley & Sons, Inc.