Lifting theorems and facet characterization for a class of clique partitioning inequalities (Q1306454)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lifting theorems and facet characterization for a class of clique partitioning inequalities |
scientific article |
Statements
Lifting theorems and facet characterization for a class of clique partitioning inequalities (English)
0 references
19 December 1999
0 references
In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the compact graph \(K_m\) on \(m\) vertices, it defines a facet for the polytope corresponding to \(K_n\) for all \(n>m\). This answers a question raised by Grötschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets.
0 references
polyhedral combinatorics
0 references
facets
0 references
lifting
0 references
clique partitioning
0 references