The minimum cut problem is a well-solved special case of submodular function minimization. We show that it is in fact equivalent to minimizing a modular function over a ring family. Onehalf of this equivalence follows from classical work of Rhys and Picard. We give a number of applications to testing membership in special kinds of matroid polyhedra.
1. Introduction
Let f be a function defined on subsets of S. I f f satisfies
for all A, B S, then f is submodular. We say that f is supermodular if -f is submodular, and that f is modular if it is both sub-and supermodular. Submodular function minimization is the problem: Given f , available via an oracle which for any A C S, gives f(A), find A C S such that f(A) is minimum. There is a polynomialtime algorithm (polynomial in IS1 and the logarithm of maxlf(A)l) for this problem [6], based on the ellipsoid algorithm, but no combinatorial solution algorithm is known.
An important and well-known instance of submodular function minimization is the network minimum cut problem. Here we are given a digraph G = (V,E), a positive edge capacity ui for each j E E, and distinguished vertices r, s E V. We wish to find a set A, r E A C V{s}, such that u(6(A)) is minimized. (Some notation: ForA V, 6(A) denotes G E E : j leaves A} and ?(A) denotes G E E: both ends of j are in A}. For a vector ( a i : i E I ) and J C I, a(J) denotes Z ( a i : i E J ) . ) The function f defined on subsets of S = V{r,s} by f(A) = u(6(A U {r})) is easily shown to be submodular, and the minimum cut problem is equivalent to minimizing f .