On minimizing symmetric set functions

Mader proved that every loopless undirected graph contains a pair (u, v) of nodes such that the star of v is a minimum cut separating u and v. Nagamochi and Ibaraki showed that the last two nodes of a “max-back order” form such a pair and used this fact to develop an elegant min-cut algorithm. M. Queyranne extended this approach to minimize symmetric submodular functions. With the help of a short and simple proof, here we show that the same algorithm works for an even more general class of set functions.