On the dominant of the s-t-cut polytope: Vertices, facets, and adjacency

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 ${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$ of the s-t-cut polytope. We present a complete characterization of ${{\ensuremath{P_{s-t-{\rm cut}}}^{\uparrow}}}$ with respect to vertices, facets, and adjacency.