Thumbnail Image

On the dominant of the `s`-`t`-cut polytope

Skutella, Martin; Weber, Alexia

Inst. Mathematik

The natural linear programming formulation of the maximum s-t-flow problem in path-variables has a dual linear program whose underlying polyhedron is the dominant of the s-t-cut polytope. We present a complete characterization of this polyhedron with respect to vertices, facets, and adjacency.