Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions

Abstract
In this paper we present a class of valid inequalities as well as a class of facets for the cut-polytope of the complete graph. It is shown that many of the known classes of valid inequalities, e.g., triangle, hypermetric and cycle inequalities, belong to this class. By specializing some of the parameters, large classes of facets can be defined. It is shown that each of these classes contains at least (n/3)n/3 facets, where n ≥ 10 denotes the number of vertices, and that the corresponding separation problems are polynomially solvable. These results are based on a one-to-one correspondence established between the set of valid inequalities (facets) for the cut-polytope of Kn+1, and the set of nonnegative (extremal) quadratic pseudo-Boolean functions in n variables.

This publication has 0 references indexed in Scilit: