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

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 K_n+1, and the set of nonnegative (extremal) quadratic pseudo-Boolean functions in n variables.