Some new classes of facets for the equicut polytope Original Research Article

Given a graph G = (V, E), a cut in G that partitions V into two sets with ⌊12¦V¦⌋ and ⌈12¦V¦⌉ nodes is called an equicut. Suppose that there are weights assigned to the edges in E. The problem of finding a minimum weight equicut in G is known to be NP-hard. The equicut polytope is defined as the convex hull of the incidence vectors of the equicuts in G. In this paper we describe several new classes of facets for the equicut polytope; they arise as various generalizations of an inequality based on a cycle introduced by Conforti et al. (1990). Most of our inequalities have the interesting feature that their support graphs are planar but for some of them both planarity and connectivity properties are lost. Finally we show how our results can be applied to obtain new classes of facets for the cut polytope.