On the k-cut subgraph polytope

The authors consider the problem of finding a minimum-cost set of k-pairwise-disjoint (s,t)-cuts in a graph. For non-negative costs, this problem was solved independently by Nishihara and Inoue, and Wagner. Both solutions involve formulating the problem as a linear-programming problem. In this paper, the authors give new polyhedral interpretations of the problem. Relationships to the path formulation of the maximum-flow problem are also established.