Maximum concurrent flows and minimum cuts (Q1194345)

Let \(f(X,\overline X)\) be any symmetric function representing the cost of cuts \((X,\overline X)\) in a network. The authors show the \(n-1\) minimum cost cuts are always sufficient to separate all pairs of nodes, and they propose an algorithm to find the set of these essential cuts with \(n-1\) oracle calls [improving the result of \textit{R. Hassin}, Math. Oper. Res. 13, No. 4, 535-542 (1988; Zbl 0667.90034)]. The authors also consider \(k\)-way partitions, and, using linear programming techniques, prove the following result (independently obtained with combinatorial arguments by \textit{F. Shahrokhi} and \textit{D. W. Matula} [``The maximum concurrent flow problem'', Tech. Rep., New Mexico Tech. (1986)]): If the saturated arcs in a multicommodity flow problem form a \(k\)-way partition, \(k\leq 4\), then the \(k\)-way partition contains a two-way partition, which is the minimum weight sparsest cut.