The equipartition polytope. II: Valid inequalities and facets

Theequipartition problem is defined as follows: given a graphG = (V, E) and edge weightsc_e, partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we describe some facet inducing inequalities of this polytope.Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.