Optimizing over Semimetric Polytopes

A new combinatorial structure, the semicut in a graph, is defined as a generalization of a cut. Extreme semicuts are shown to be associated with the vertices of the rooted semimetric polytope. Such a polytope provides a linear relaxation of the cut polytope whose integer points correspond to all the cuts of a graph. Thus, optimizing over the set of all semicuts yields an upper bound for the maximum weight cut problem. An efficient combinatorial algorithm that finds an optimal semicut is described. Such an algorithm is based on the computation of a fractional bidirected flow