A Combinatorial Strongly Polynomial Algorithm for
Minimizing Submodular Functions
SATORU IWATA
University of Tokyo, Tokyo, JapanLISA FLEISCHER
Carnegie Mellon University, Pittsburgh, Pennsylvania

AND
SATORU FUJISHIGE
Osaka University, Osaka, Japan

Abstract. This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The
algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying
set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded
by a polynomial in the size of the underlying set and the length of the largest absolute function value.
The paper also presents a strongly polynomial version in which the number of steps is bounded by apolynomial in the size of the underlying set, independent of the function values.

A preliminary version has appeared in Proceedings of the 32nd Annual ACM Symposium on Theoryof Computing (Portland, Ore.). ACM, New York, 2000, pp. 96–107.
The work of S. Iwata was done at Osaka University, Toyonaka, Japan and at the Fields Institute,
Toronto, Ont., Canada.
The work of S. Iwata was partly supported by Grants-in-Aid for Scientific Research from the Ministryof Education, Science, Sports, and Culture of Japan.
The work of L. Fleischer was done while on leave at the Center for Operations Research and Econometrics, Universite Catholique de Louvain, Belgium and at the Fields Insititute, Toronto, Ont., Canada.
The work of L. Fleischer was supported in part by DONET, a European network supported by theEuropean Community with the frame of the Training and Mobility of Researchers Programme (Contract number ERB TMRX-CT98-0202). Additional support was from the University of Waterloo, Dept.
of Combinatorics and Optimization, and the National Science Foundation (NSF) through grants INT
99-02663 and EIA 99-73858.
The work of S. Fujishige was partly supported by Grants-in-Aid for Scientific Research from the
Ministry of Education, Science, Sports, and Culture of Japan.
Authors’ addresses: S. Iwata, Department of Mathematical Engineering and Information Physics, University of Tokyo, Tokyo 113-8656, Japan, e-mail: iwata@sr3.t.u-tokyo.ac.jp; L. Fleischer, Graduate
School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213, e-mail:lkf@andrew.cmu.edu; S. Fujishige, Division of Systems Science, Graduate School of Engineering
Science, Osaka University, Toyonaka, Osaka 560-8531, Japan, e-mail: fujishig@sys.es.osaka-u.ac.jp.
Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted
without fee provided that the copies are not made or distributed for profit or commercial advantage,
the copyright notice, the title of the publication, and its date appear, and notice is given that copying
is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
°
C 2001 ACM 0004-5411/01/0700-0761 $5.00
Journal of the ACM, Vol. 48, No. 4, July 2001, pp. 761–777.

762

S. IWATA ET AL.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics—combinatorial algorithms
General Terms: Algorithms
Additional Key Words and Phrases: Discrete optimization, strongly polynomial algorithm, submodular
function

1. Introduction
Let V be a finite nonempty set of cardinality n. A function f defined on all thesubsets of V is called submodular if it satisfies
f (X ) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ),∀X, Y ⊆ V.

This paper presents a combinatorial polynomial-time algorithm for finding a minimizer of a general submodular function, provided that an oracle for evaluating
the function value is available. Throughout this paper, we assume without loss ofgenerality that f (∅) = 0 by subtracting the scalar f (∅) from every function value.
Submodularity is a discrete analog of convexity [Frank 1982; Fujishige 1984b;
Lovász 1983], and submodular functions arise naturally in various fields, including
combinatorial optimization, computational biology, game theory, scheduling, probability, and information theory. Examples include the matroid rank function, thecut capacity function, and the entropy function. Problems in diverse areas such as
dynamic flows [Hoppe and Tardos 2000], facility location [Tamir 1993], and multiterminal source coding [Fujishige 1978; Han 1979] rely on algorithms for general
submodular function minimization. Submodular function minimization is also used
to solve submodular flow problems [Cunningham and Frank 1985; Edmonds andKarp 1972; Fujishige and Iwata 2000] which generalize network flow and matroid
optimization problems, and model several graph augmentation and connectivity
problems [Edmonds and Giles 1977; Frank and Tardos 1988; 1989]. For general background on submodular functions, see Frank and Tardos [1998], Fujishige[1991], and Lovász [1983].
There are two natural polyhedra in RV associated with a submodular function
f . The submodular polyhedron P( f ) and the base polyhedron B( f ) are defined by
P( f ) = {x | x ∈ RV , ∀X ⊆ V : x(X ) ≤ f (X )},B( f ) = {x | x ∈ P( f ), x(V ) = f (V )},P
where x(X ) = v∈X x(v). Linear optimization problems over these polyhedra canbe solved efficiently by the greedy algorithm [Edmonds 1970].
The first polynomial-time algorithm for submodular function minimization isdue to Grötschel et al. [1981]. They showed, in general, the polynomial-time
equivalence of separation and optimization for polyhedra via the ellipsoid method.
The separation problem of deciding whether 0 ∈ P( f µ ), for the submodular function f µ defined by subtracting scalar µ ≤ 0 from f (X ) for every nonempty X ⊆ V ,is equivalent to determining if the minimum of the submodular function f is at leastµ. This problem can be solved using the ellipsoid algorithm in conjunction with thegreedy algorithm that solves the optimization problem over P( f µ ). Since the maximum value µ∗ of µ with 0 ∈ P( f µ ) equals the minimum value of f , embedding theellipsoid algorithm in a binary search for µ∗ yields a polynomial-time algorithm

Minimizing Submodular Functions

763

for submodular function minimization. However, the ellipsoid method is far frombeing efficient in practice and is not combinatorial.
In this paper, we present a combinatorial polynomial-time algorithm for submodular function minimization. Our algorithm uses an augmenting path approachwith reference to a convex combination of extreme points of the associated basepolyhedron. Such an approach was first introduced by Cunningham [1984] forminimizing submodular functions that arise from the separation problem for matroid polyhedra. This was adapted for general submodular function minimization
by Bixby et al. [1985] and improved by Cunningham [1985] to obtain the first combinatorial, pseudopolynomial-time algorithm. More recently, Narayanan [1995]
introduced a rounding technique that improves Cunningham’s algorithm for matroid polyhedra. Based on a minimum-norm base characterization of minimizers[Fujishige 1980; 1984a], Sohoni [1992] devised another pseudopolynomial-timealgorithm. For a closely related problem of finding a nonempty proper subset thatminimizes a symmetric submodular function f , Queyranne [1998] has described a
combinatorial strongly polynomial algorithm. (A symmetric set function f satisfies
f (X ) = f (V \X ) for all X ⊆ V .) Queyranne’s algorithm extends the undirected
minimum-cut algorithm of Nagamochi and Ibaraki [1992].
A fundamental tool in the above algorithms for general submodular function
minimization [Bixby et al. 1985; Cunningham 1984; 1985; Narayanan 1995] is to
move from one extreme point of the base polyhedron to an adjacent extreme point
via an exchange operation that increases one coordinate and decreases anothercoordinate by the same quantity. This quantity is called the exchange capacity.
These previous methods maintain a directed graph with a vertex set given by theunderlying set of the submodular function, and with an arc set that represents a
set of possible exchange operations. They progress by iteratively performing asequence of exchange operations along an augmenting path. These algorithms are
not known to be polynomial since the best-known lower bound on the amountof each augmentation is too small. The amount of augmentation is determinedby exchange capacities multiplied by the convex combination coefficients. These
coefficients may be as small as the reciprocal of the maximum absolute value ofthe submodular function.
To make a pseudopolynomial-time algorithm run in polynomial time, Edmonds
and Karp [1972] introduced the scaling technique in the design of the firstpolynomial-time minimum cost flow algorithm. Since this initial success, there
have been many polynomial-time scaling algorithms designed for various combinatorial optimization problems. However, a straightforward attempt to apply thescaling technique does not work for submodular function minimization. This ismainly because rounding a submodular function may violate the submodularity.
More specifically, the set function f 0 defined by f 0 (X ) = b f (X )c is not necessarily submodular even if f is a submodular function.
To overcome this difficulty, we employ a scaling framework that uses the complete directed graph on the underlying set, letting the capacity of this arc set depend
directly on the scaling parameter δ. The complete directed graph serves as a relaxation of the submodular function f to another submodular function f δ defined byf δ (X ) = f (X ) + δ |X | · |V \X |. Note that the second term δ |X | · |V \X | is the cut
function of this additional graph, and hence submodular.
The relaxation f δ has a natural interpretation in the setting of network flows. In
their cut-canceling algorithm for minimum cost flows, Ervolina and McCormick

764

S. IWATA ET AL.

[1993] relax the capacity of each flow arc by the scaling parameter δ. For submodular
function minimization, the “graph” is the set of possible exchange arcs, which isreally the complete directed graph on V .
The use of this additional graph was first introduced by Iwata [1997] as the firstcapacity-scaling algorithm for submodular flow. Since that paper was published,
the submodular flow algorithms of Iwata et al. [1999] and Fleischer et al. [2001]
have developed the techniques further. In particular, incorporating ideas from Iwata
et al. [1999], the algorithm in Fleischer et al. [2001] introduces a method to avoid
exchange operations on an augmenting path. This is done by carefully performing
exchange operations during the search for an augmenting path of sufficient residual
capacity. Our work in the present paper employs this technique to develop a capacity
scaling, augmenting path algorithm for submodular function minimization.
The resulting algorithm uses O(n 5 log M) arithmetic steps and function evaluations, where M = max{| f (X )| | X ⊆ V }. Even under the assumption that M isbounded by a constant, our scaling algorithm is faster than the best previous combinatorial, pseudopolynomial-time algorithm due to Cunningham [1985], which usesO(n 6 M log (n M)) arithmetic steps and function evaluations.
We then modify our scaling algorithm to run in strongly polynomial time. A
strongly polynomial algorithm for submodular function minimization performs a
number of steps bounded by a polynomial in the size of the underlying set, independent of M. Grötschel et al. [1988] described the first such algorithm using theellipsoid method. To make a polynomial-time algorithm run in strongly polynomial
time, Frank and Tardos [1987] developed a generic preprocessing technique that is
applicable to a fairly wide class of combinatorial optimization problems including
submodular flow (assuming an oracle for computing exchange capacities) and testing membership in matroid polyhedra. However, this framework does not readily
apply to our scaling algorithm for submodular function minimization. Instead, weestablish a proximity lemma, and use it to devise a combinatorial algorithm that repeatedly detects either a new element contained in every minimizer, a new element
not contained in any minimizer, or a new ordered pair (u, v) ∈ V such that any
minimizer containing u also contains v. The resulting algorithm uses O(n 7 log n)arithmetic steps and function evaluations. Our approach is based on the generaltechnique originated by Tardos [1985] in the design of the first strongly polynomial
minimum cost flow algorithm.
Independently, Schrijver [2000] has also developed a combinatorial strongly
polynomial algorithm for general submodular function minimization based on Cunningham’s approach. Instead of designing an algorithm that uses provably large
augmentations as we do here, Schrijver’s complexity analysis depends on an algorithmic framework that uses paths whose lengths are provably nondecreasing. His
algorithm can be shown to use O(n 8 ) function evaluations and O(n 9 ) arithmetic
steps. A modification of this algorithm improves both of these quantities by a linear
factor [Fleischer and Iwata 2000]. Both Schrijver’s algorithm and ours use Gaussian elimination to maintain the representation of a vector in B( f ) as the convex
combination of a small number of extreme points. However, we do not require thisstep to establish the polynomial time complexity of our algorithm.
Schrijver [2000] poses an open problem to design a strongly polynomial algorithm for submodular function minimization that consists only of additions, subtractions, comparisons, and oracle calls. The symmetric submodular function minimization algorithm of Queyranne [1998] is “fully combinatorial” in this sense.

Minimizing Submodular Functions

765

Iwata [2001] has very recently answered this question by describing a fully combinatorial implementation of the strongly polynomial algorithm in the present paper.
This paper is organized as follows: Section 2 provides background on submodular functions. Section 3 presents our scaling algorithm for submodular function
minimization, and Section 4 gives a strongly polynomial algorithm. In Section 5,
we discuss the variants of our algorithms without Gaussian elimination. Finally, we
conclude with extensions in Section 6.
2. Preliminaries
We denote by Z and R the set of integers and the set of reals, respectively.
P For any
vector x ∈ RV and any subset X ⊆ V , the expression x(X ) denotes v∈X x(v).
For any vector x ∈ RV , we denote by x + and x − the vectors in RV defined byx + (v) = max{0, x(v)} and x − (v) = min{0, x(v)} for v ∈ V . For each u ∈ V , letχu denote the vector in RV such that χu (u) = 1 and χu (v) = 0 for v ∈ V \{u}.
A vector in the base polyhedron B( f ) is called a base, and an extreme point ofB( f ) an extreme base. It is easy to see that for any base x ∈ B( f ) and any subset
Y ⊆ V we have x − (V ) ≤ x(Y ) ≤ f (Y ). The following fundamental lemma showsthat these inequalities are in fact tight for appropriately chosen x and Y . Although
the lemma easily follows from a theorem of Edmonds [1970] on the vector reductionof polymatroids, we provide a direct proof for completeness.
LEMMA 2.1. For a submodular function f : 2V → R, we havemax{x − (V ) | x ∈ B( f )} = min{ f (X ) | X ⊆ V }.

(2.1)

If f is integer-valued, then the maximizer x can be chosen from among integral
bases.
PROOF. Let x be a maximizer in the left-hand side. For any s, t ∈ V with
x(s) < 0 and x(t) > 0, there exists a subset X st such that s ∈ X st ⊆ V \{t} andx(X st ) = f (X st ). Then it follows from the submodularity of f that
\
[
X st
X=
s:x(s)<0

t:x(t)>0

satisfies x(X ) = f (X ). Since x(u) ≤ 0 for every u ∈ X and x(v) ≥ 0 for everyv ∈ V \X , we have x − (V ) = x(X ) = f (X ), which establishes the min-max
relation. The integrality assertion follows from the same argument starting with an
integral base x that maximizes x − (V ) over all integral bases.
It is not completely obvious that Lemma 2.1 provides a good characterizationof a minimizer of f . In fact, proving x ∈ B( f ) by the definition would require
exponential number of function evaluations. If y is an extreme base, however, there
is a compact proof that y ∈ B( f ) resulting from the greedy algorithm described
below. However, the maximizer of (2.1) may not be an extreme base. To handle
this, Cunningham [1984; 1985] suggested maintaining a base x ∈ B( f ) as a convex
combination of extreme bases, thus yielding a compact proof that x ∈ B( f ) for any
base x generated by his algorithm.
Let L = (v 1 , . . . , v n ) be a linear ordering of V . For any j ∈ {1, . . . , n}, we defineL(v j ) = {v 1 , . . . , v j }. The greedy algorithm of Edmonds [1970] and Shapley [1971]

766

S. IWATA ET AL.

computes an extreme base y ∈ B( f ) associated with L byy(v) := f (L(v)) − f (L(v)\{v}),∀v ∈ V.

(2.2)

Thus, the linear ordering L provides a certificate that y is an extreme base. Conversely, any extreme base can be generated by applying the greedy algorithm to an
appropriate linear ordering.
A fundamental tool in our algorithm is to move from a base x to another baseby an exchange operation that increases one component and decreases
P anothercomponent by the same amount, that is, x := x + α(χu − χv ). With x = i∈I λi yi ,a convex combination of extreme bases, this can be realized by applying an exchange
operation on an extreme base yi . An exchange amount β on yi corresponds to an
exchange amount λi β on x. The following lemma shows that interchanging two
consecutive elements in a linear ordering that generates yi results in an exchange
operation on yi .
LEMMA 2.2. Suppose u immediately succeeds v in a linear ordering L thatgenerates an extreme base y ∈ B( f ). Then the linear ordering L 0 obtained from L
by interchanging u and v generates an extreme base y 0 = y + c̃(y, u, v)(χu − χv )withc̃(y, u, v) = f (L(u)\{v}) − f (L(u)) + y(v).

(2.3)

PROOF. It is obvious from the greedy algorithm that y 0 can differ from y only
at u and v. Namely, y 0 = y + β(χu − χv ) for some β. Since L 0 (v) = L(u), it
follows from (2.2) that y 0 (v) = f (L(u)) − f (L(u)\{v}). Thus, we obtain β =f (L(u)\{v}) − f (L(u)) + y(v).
The quantity c̃(y, u, v) in Lemma 2.2 is called an exchange capacity. In general,an exchange capacity c̃(x, u, v) is defined for any base x ∈ B( f ) and any orderedpair of distinct u, v ∈ V as the maximum amount of exchange operation that keeps
x in the base polyhedron. Hence, the exchange capacity c̃(x, u, v) is expressed asc̃(x, u, v) = min{ f (X ) − x(X ) | u ∈ X ⊆ V \{v}}.

(2.4)

However, there is nothing special that makes this computation easier than minimizing f . Our algorithm uses only those exchange capacities that can be computed via
Lemma 2.2.
3. A Scaling Algorithm
In this section, we describe a combinatorial algorithm for minimizing an integervalued submodular function f: 2V → Z with f (∅) = 0. We assume we have an
evaluation oracle for the function value of f . Our algorithm is an augmenting path
algorithm, embedded in a scaling framework. A formal description of this algorithm
SFM appears in Figure 1.
3.1. THE SCALING FRAMEWORK. The algorithm consists of scaling phases witha positive parameter δ. The algorithm starts with an arbitrary linear ordering L on
V and the extreme base x ∈ B( f ) generated by L. The initial value of δ is given byδ := ξ/n 2 with ξ = min{|x − (V )|, x + (V )}. At the end of each scaling phase, thealgorithm cuts δ in half. The algorithm ends with δ < 1/n 2 .

Minimizing Submodular Functions

767

FIG. 1. A scaling algorithm for submodular function minimization. The algorithm finds a subsetof V that minimizes submodular function f . It uses a directed graph G ◦ = (V, A◦ ) where A◦ ={(u, v) | u, v ∈ V, u 6= v, ϕ(u, v) = 0}.

To adapt the augmenting path approach to this scaling framework, we use acomplete directed graph on V with arc capacities that depend directly on our scaling
parameter δ. Let ϕ: V ×V → R be a flow in the complete directed graph G = (V, A)
with the vertex set V and the arc set A = V × V . The boundary ∂ϕ: V → R is
defined byXX
ϕ(u, v) −ϕ(v, u),∀u ∈ V.
(3.1)∂ϕ(u) =v∈V

v∈V

That is, ∂ϕ(u) is the net flow value emanating from u. A flow ϕ is called δ-feasible if
it satisfies capacity constraints 0 ≤ ϕ(u, v) ≤ δ for every u, v ∈ V . Our algorithm
maintains ϕ such that at least one of ϕ(u, v) and ϕ(v, u) is equal to zero for anyu, v ∈ V .
P
The algorithm maintains a base x ∈ B( f ) as a convex combination x = i∈I λi yi
of extreme bases yi ∈ B( f ). For each index i ∈ I , the algorithm also maintains alinear ordering L i that generates yi . Instead of trying to maximize x − (V ) directly,
the algorithm uses z = x + ∂ϕ and seeks to increase z − (V ), thereby increasingx − (V ) via the δ-feasibility of ϕ. This z is a base in the base polyhedron of thesubmodular function f δ (X ) = f (X ) + δ|X | · |V \X |.

768

S. IWATA ET AL.

3.2. A SCALING PHASE. Each δ-scaling phase maintains a δ-feasible flow ϕ
and a subgraph G ◦ = (V, A◦ ) with the arc set A◦ = {(u, v) | u, v ∈ V, u 6=v, ϕ(u, v) = 0}. The δ-scaling phase aims at increasing z − (V ) by sending flow
along directed paths in G ◦ from S = {v | v ∈ V, z(v) ≤ −δ} to T = {v | v ∈ V,z(v) ≥ δ}. Such a directed path is called a δ-augmenting path.
If there is no δ-augmenting path, let W denote the set of vertices currently reachable from S in G ◦ . A triple (i, u, v) of i ∈ I , u ∈ W and v ∈ V \W is called
active if u immediately succeeds v in L i . If there is an active (i, u, v), the algorithm
performs an appropriate exchange operation, and modifies ϕ so that z = x + ∂ϕ isinvariant. We refer to this procedure as Double-Exchange(i, u, v). The detail of
Double-Exchange is described below. As a result of Double-Exchange(i, u, v),
either W remains unchanged or the vertex v and the set of vertices in V \Wreachable from v by δ-capacity paths are added to W . The algorithm performs
Double-Exchange as long as it is applicable, until a δ-augmenting path is found.
Once a δ-augmenting path P is found, the algorithm augments the flow ϕ by δalong P by setting ϕ(u, v) := δ − ϕ(v, u) and ϕ(v, u) := 0 for each arc (u, v) in P.
This increases z − (V ) by δ since z changes only at the initial and terminal verticesof P. This is an extension of a technique developed in Fleischer et al. [2001] forfinding δ-augmenting paths for submodular flows.
A δ-scaling phase ends when there is neither a δ-augmenting path nor an active
triple. Then the algorithm cuts the value of δ in half and goes to the next scaling
phase. To keep the δ-feasibility of ϕ, the algorithm halves the flow ϕ for each arc.
The first step of the procedure Double-Exchange(i, u, v) is to compute theexchange capacity c̃(yi , u, v). It then updates x and ϕ as x := x + α(χu − χv ) andϕ(u, v) := ϕ(u, v) − α, so that z = x + ∂ϕ remains unchanged. The amount αof this exchange operation is determined by taking the minimum of ϕ(u, v) andλi c̃(yi , u, v). Note that ϕ(u, v) is the maximum amount of feasible decrease offlow Pon (u, v) and that λi c̃(yi , u, v) is the maximum exchange possible to effect in
x = i λi yi by performing an exchange operation on yi and keeping all the otherextreme bases in I fixed.
The procedure Double-Exchange(i, u, v) updates yi := yi +c̃(yi , u, v)(χu −χv )and λi := α/c̃(yi , u, v). It also updates L i by interchanging u and v, which
maintains yi as an extreme base generated by L i . Double-Exchange(i, u, v)
is called saturating if α = λi c̃(yi , u, v). Otherwise, it is called nonsaturating.
If Double-Exchange(i, u, v) is nonsaturating, the old yi remains in theconvex representation of x with coefficient λi − α/ c̃(yi , u, v). Thus, if
Double-Exchange(i, u, v) is nonsaturating, then before updating yi , it adds toI a new index k with yk := yi , λk := λi − α/ c̃(yi , u, v), and L k := L i .
Double-Exchange(i, u, v) is summarized in Figure 2.
After each δ-augmentation, and at the end of the δ-scaling phase, the algorithm
applies a procedure Reduce(x, I ) that computes an expression for x as a convex
combination of (at most n) affinely independent extreme bases yi , chosen fromthe current yi ’s. This computation is a standard linear programming technique oftransforming a feasible solution into a basic feasible solution. If the set of extreme
points are not affinely independent, P
there is a set of coefficientsµi for i ∈ I thatP
µi = 0. Using Gaussian
is not identically zero and satisfiesµi yi = 0 andelimination, we can start computing such µi until a dependency is detected. At thispoint, we eliminate the dependency by computing θ := min{λi /µi | µi > 0} andupdating λi := λi − θ µi for i ∈ I . At least one i ∈ I satisfies λi = 0. Delete

Minimizing Submodular Functions

769

Double-Exchange(i, u, v):c̃(yi , u, v) ← f (L i (u)\{v}) − f (L i (v)) + yi (v)α ← min{ϕ(u, v), λi c̃(yi , u, v)}
x ← x + α(χu − χv )ϕ(u, v) ← ϕ(u, v) − α
If α < λi c̃(yi , u, v) thenk ← a new index
I ← I ∪ {k}λk ← λi − α/c̃(yi , u, v)
λi ← α/c̃(yi , u, v)
yk ← yi
Lk ← Liyi ← yi + c̃(yi , u, v)(χu − χv )Update L i by interchanging u and v.

FIG. 2. Algorithmic description of the procedure Double-Exchange(i, u, v).

such i from I . We continue this procedure until we eventually obtain affine
independence.
This same step is also used in the submodular function minimization algorithmsof Cunningham [1985] and Schrijver [2000]. However, for the present algorithm,
we do not need this step to obtain a polynomial bound on the complexity. We include
this linear algebraic procedure because it significantly reduces the running time of
the algorithm. For an analysis of the algorithm without Reduce, see Section 5.
3.3. CORRECTNESS. In the subsequent analysis, the end of a scaling phase refers
to the point immediately before δ is cut in half. The following lemma establishes arelaxed strong duality, which plays a crucial role in the analysis of our algorithm.
LEMMA 3.1. At the end of the δ-scaling phase, z − (V ) ≥ f (W ) − nδ.
PROOF. At the end of the δ scaling phase, there are no active triples, which
implies for each i ∈ I the first |W | vertices in
PL i must belong
P to W . Then it follows
(W
)
=
f
(W
).
Since
x
=
λ
y
and
from (2.2)
thatyii∈I i ii∈I λi = 1, we obtainPx(W ) = i∈I λi yi (W ) = f (W ).
At the end of the δ scaling phase, the set W also satisfies S ⊆ W ⊆ V \T and∂ϕ(W ) ≥ 0. By the definitions of S and T , we have z(v) < δ for every v ∈ W andz(v) > −δ for every v ∈ V \W . Therefore, we have z − (V ) = z − (W )+z − (V \W ) ≥z(W ) − δ|W | − δ|V \W | = x(W ) + ∂ϕ(W ) − nδ ≥ f (W ) − nδ.
As an immediate consequence of Lemma 3.1, we obtain the following lemma,
which leads us to the correctness of the scaling algorithm.
LEMMA 3.2. At the end of the δ-scaling phase, x − (V ) ≥ f (W ) − n 2 δ.
PROOF. By Lemma 3.1, the set W satisfies z − (V ) ≥ f (W )−nδ. Since ∂ϕ(v) ≤(n − 1)δ for each v ∈ V , we have x − (V ) ≥ z − (V ) − n(n − 1)δ ≥ f (W ) − n 2 δ.
THEOREM 3.3. The algorithm obtains a minimizer of f at the end of the δscaling phase with δ < 1/n 2 .

770

S. IWATA ET AL.

PROOF. By Lemma 3.2, the output W of the algorithm satisfies x − (V ) ≥f (W ) − n 2 δ > f (W ) − 1. For any Y ⊆ V , the weak duality in Lemma 2.1
asserts x − (V ) ≤ f (Y ), which implies f (W ) − 1 < f (Y ). Hence, it follows fromthe integrality of f that W minimizes f .
3.4. COMPLEXITY. We now investigate the number of iterations in each scaling phase.
LEMMA 3.4. The number of augmentations per scaling phase is O(n 2 ).
PROOF. It follows from Lemma 3.1 that at the beginning of the δ-scaling phase
except for the first one, z − (V ) is at least f (X ) − 2nδ for some X ⊆ V . Replacing
ϕ by ϕ/2 could decrease z(X ) by at most |X | · |V \X |δ which is bounded above
by n 2 δ/4 for any X , and hence the decrease of z − (V ) is also bounded by n 2 δ/4.
Hence, f (X ) − 2nδ − n 2 δ/4 ≤ z − (V ). On the other hand, since x(X ) ≤ f (X ) and∂ϕ(X ) ≤ δ|X | · |V \X |, we have z − (V ) ≤ z(X ) ≤ f (X ) + n 2 δ/4 throughout theδ-scaling phase. Since each δ-augmentation increases z − (V ) by δ, the number ofδ-augmentations per phase is at most 2n + n 2 /2, which is O(n 2 ), for all phases after
the first one.
In the first phase, let x denote the initial extreme base. Then z = x at the startof the algorithm. Since z − (V ) ≤ f (∅) = 0 and z − (V ) ≤ f (V ) = x(V ) must holdthroughout, possible increase of z − (V ) during the first scaling phase is bounded byξ = min{|x − (V )|, x + (V )}. Thus, the initial setting δ = ξ/n 2 guarantees that the
number of augmentations in the first scaling phase is n 2 .
LEMMA 3.5. Between δ-augmentations, |I | grows by at most n − 1.
PROOF. A new index is added to I only during a nonsaturating
Double-Exchange. Since each nonsaturating Double-Exchange adds a newelement to W , this happens at most n − 1 times before a δ-augmenting path
is found.
LEMMA 3.6. Algorithm SFM performs the procedure Double-ExchangeO(n 3 ) times between δ-augmentations.
PROOF. Once the algorithm applies Double-Exchange(i, u, v), the vertices uand v are interchanged in L i , and the triple (i, u, v) never becomes active again
until the next δ-augmentation or the end of the phase. By performing basis reduction
after each augmentation, |I | < 2n throughout the algorithm by Lemma 3.5. Hence,
the number of times Double-Exchange is applied is bounded by the number of
triples, which is at most O(n 3 ).
THEOREM 3.7. Algorithm SFM is a polynomial-time algorithm that performsO(n 5 log M) function evaluations and arithmetic operations.
PROOF. The algorithm starts with δ = ξ/n 2 and ends with δ < 1/n 2 . For the
initial extreme base x and X = {v | v ∈ V, x(v) > 0}, we have ξ ≤ x + (V ) =x(X ) ≤ f (X ) ≤ M. Thus, SFM consists of O(log M) scaling phases. Each scaling
phase performs O(n 2 ) augmentations by Lemma 3.4.
Between δ-augmentations, there are O(n 3 ) calls of Double-Exchange byLemma 3.6. The procedure Double-Exchange consists of O(1) calls of the function evaluation oracle. Therefore, the algorithm calls the oracle O(n 5 log M) times
in total.

Minimizing Submodular Functions

771

As a result of Double-Exchange(i, u, v), the vertex v and the set of vertices
in V \W reachable from v by δ-capacity paths may be added to W . (This set may
be determined by standard graph search on G.) Thus, over the course of an augmentation, updates to W take at most n 3 time. To find an active triple efficiently,
we maintain a pointer for each index i ∈ I that points to an element of W in an
active triple for L i . After a Double-Exchange that does not increase W , this takes
at most linear time to update. After a Double-Exchange that increases W , thismay need to be updated for all i ∈ I , and thus takes at most n 2 time. Thus, peraugmentation, this takes O(n 3 ) time. After augmenting ϕ on P, the endpoints of P
may be removed from S or T .
P
After each augmentation, we also update the expression x = i∈I λi yi to recover
the affine independence of yi ’s. The bottleneck in this procedure is the time spentfor computing the coefficients µi , as described in Section 3.2. Since |I | < 2n by
Lemma 3.5, this takes O(n 3 ) arithmetic operations. If performed correctly, theencoding length of the numbers generated by Gaussian elimination is bounded by apolynomial in the size of the input (which includes the maximum encoding lengthof the function values) [Edmonds 1967]. In addition, since the resulting multipliers
λ = (λi | i ∈ I ) are a basic solution to the system H λ = x where the columnsof H correspond to extreme bases yi , their size is also bounded by a polynomialin the input size. Thus, SFM is a polynomial-time algorithm with O(n 5 log M)
arithmetic steps.
The previous best known pseudopolynomial time bound is O(n 6 M log(n M))
due to Cunningham [1985]. Theorem 3.7 shows that our scaling algorithm is fasterthan this even if M is fixed as a constant.
In this section, we have shown a weakly polynomial-time algorithm for minimizing integer-valued submodular functions. The integrality of a submodular function
f guarantees that if we have a base x ∈ B( f ) and a subset X of V such thatf (X ) − x − (V ) is less than one, X is a minimizer of f . Except for this, we have notused the integrality of f . It follows that for any real-valued submodular function
f : 2V → R, if we are given a positive lower bound ² for the difference between
the second minimum and the minimum value of f , the present algorithm works forthe submodular function (1/²) f with an O(n 5 log(M/²)) bound on the number ofsteps, where M = max{| f (X )| | X ⊆ V }.

4. A Strongly Polynomial Algorithm
This section presents a strongly polynomial algorithm for minimizing a real-valued
submodular function f: 2V → R. The main idea is to show via Lemma 4.1 belowthat after O(log n) scaling phases, the algorithm detects either a new element thatis contained in every minimizer of f , a new element that is not contained in any
minimizer of f , or a new vertex pair (u, v) such that v is in every minimizer off containing u. Since there are O(n 2 ) such detections, after O(n 2 log n) scaling
phases, the algorithm finds a minimizer of f .
LEMMA 4.1. At the end of the δ-scaling phase in SFM( f ), the following hold:(a) If x(w) < −n 2 δ, then w is contained in every minimizer of f .
(b) If x(w) > n 2 δ, then w is not contained in any minimizer of f .

772

S. IWATA ET AL.

PROOF. By Lemma 3.2, x − (V ) ≥ f (W ) − n 2 δ holds at the end of the δ-scaling
phase. For any minimizer X of f , we have f (W ) ≥ f (X ) ≥ x(X ) ≥ x − (X ). Thus,x − (V ) ≥ f (W ) − n 2 δ ≥ x − (X ) − n 2 δ. Therefore, if x(w) < −n 2 δ, then w ∈ X .
On the other hand, x − (X ) ≥ x − (V ) ≥ f (W ) − n 2 δ ≥ x(X ) − n 2 δ. Therefore, if/ X.
x(w) > n 2 δ, then w ∈The strongly polynomial algorithm, denoted SPM( f ), maintains a subset X ⊆ V
that is included in every minimizer of f , a vertex set U = {u 1 , . . . , u ` } corresponding to a partition {V1 , . . . , V` } of V \X into pairwise disjoint nonempty subsets, a
submodular function fˆ defined on 2U , and a directed acyclic graph D = (U, F).
Each arc in F is an ordered pair (u, w) of vertices u and w in U such that w is in
every minimizer of fˆ containing u. For u ∈ U , let 0(u) denote the corresponding
set of the partition of V \X . For example, 0(u j ) = V j . For Y ⊆ U , we also denote0(Y ) = ∪u∈Y 0(u). Throughout the algorithm, we keep a correspondence between
minimizers of f and fˆ so that any minimizer of f is represented as X ∪ 0(W ) forsome minimizer W of fˆ . Initially, the algorithm assigns U := V , F := ∅, fˆ := f ,and X := ∅, which clearly satisfy the above properties.
Let R(u) denote the set of the vertices reachable from u ∈ U in D. We denoteby fˆ u the contraction of fˆ by R(u), that is, the submodular function on ground set
U \R(u) defined byfˆ u (Y ) = fˆ (Y ∪ R(u)) − fˆ (R(u)),∀Y ⊆ U \R(u).

(4.1)

A linear ordering (u 1 , . . . , u ` ) of U is called consistent with D if (u i , u j ) ∈ F
implies that j < i. The extreme base generated by a consistent linear ordering is
also called consistent.
LEMMA 4.2. Any consistent extreme base y ∈ B( fˆ ) satisfies y(u) ≤ fˆ (R(u))−ˆf (R(u)\{u}) for each u ∈ U .
PROOF. The consistent extreme base y satisfies y(u) = fˆ (Y ) − fˆ (Y \{u}) forsome Y ⊇ R(u). The claim then follows from the submodularity of fˆ .
The building block of the strongly polynomial algorithm is the subroutine
Fix( fˆ , D, η) which performs O(log n) scaling phases starting with δ = η, andan extreme base y ∈ B( fˆ ) that is consistent with D for submodular function fˆ .
The subroutine Fix( fˆ , D, η) is invoked only if fˆ (U ) ≥ η/3 or there is a subset Y ⊆ U such that fˆ (Y ) ≤ −η/3. Fix( fˆ , D, η) performs scaling phases untilδ < η/3n 3 . Then, if fˆ (U ) ≥ η/3, at least one element w ∈ U satisfies x(w) > n 2 δat the end of the last scaling phase. By Lemma 4.1 (b), such an element w is notcontained in any minimizer of fˆ . Otherwise, fˆ (Y ) ≤ −η/3 and at least one elementw ∈ Y satisfies x(w) < −n 2 δ at the end of the last scaling phase. By Lemma 4.1(a), such an element w is contained in every minimizer of fˆ .
The choice of η in each call to Fix is determined so that (i) Lemma 4.1 may
be invoked for a new element w after O(log n) phases, and (ii) the number ofaugmentations in the first phase is not too large. This is accomplished by setting
η as in (4.2). We explain why (i) holds below, and why (ii) holds in the proof of
Theorem 4.3
η = max{ fˆ (R(u)) − fˆ (R(u)\{u}) | u ∈ U }.
(4.2)

Minimizing Submodular Functions

773

Lemma 4.2 implies that y(v) ≤ η for any y ∈ B( fˆ ) consistent with D.
If η ≤ 0, then an extreme base y ∈ B( fˆ ) consistent with D satisfies y(u) ≤ 0
for each u ∈ U . In this case, y − (U ) = y(U ) = fˆ (U ), which implies that U
minimizes fˆ by the weak duality in Lemma 2.1. Therefore, the algorithm returns
U as a minimizer of fˆ .
If η > 0, then let u be an element that attains the maximum in the right-handside of (4.2). Then, since η = fˆ (R(u)) − fˆ (R(u)\{u}) = fˆ (U ) − fˆ (R(u)\{u}) +( fˆ (R(u)) − fˆ (U )), at least one of the three values, fˆ (U ), − fˆ (R(u)\{u}), andfˆ (R(u)) − fˆ (U ), is greater than or equal to η/3. Hence, we consider the following
three cases:
If fˆ (U ) ≥ η/3 > 0, the algorithm applies Fix( fˆ , D, η) to find a new element w
that is not in any minimizer of fˆ . In this case, it suffices to minimize the functionfˆ among those subsets that do not contain any vertex v with w ∈ R(v). Thus, thealgorithm deletes {v | w ∈ R(v)} from U .
If fˆ (R(u)\{u}) ≤ −η/3 < 0, the algorithm applies Fix( fˆ , D, η) to find a newelement w in every minimizer of fˆ . In this case, every minimizer of fˆ includes
R(w). Thus, it suffices to minimize the submodular function fˆ w , defined on thesmaller underlying set U \R(w) as in (4.1); so the algorithm sets fˆ := fˆ w .
Otherwise, ( fˆ u (U \R(u)) = fˆ (U ) − fˆ (R(u)) ≤ −η/3 < 0), the algorithm
applies Fix( fˆ u , Du , η) where Du is defined as D restricted to U \R(u). In this case,Fix( fˆ u , Du , η) finds an element w ∈ U \R(u) that is contained in every minimizerof fˆ u . Thus, the algorithm adds (u, w) to F. If this creates a cycle in D, then the arcsof the cycle imply that either every element in the cycle is contained in a minimizerof fˆ , or every element in the cycle is not contained in any minimizer. Thus, thealgorithm contracts the cycle to a single vertex and modifies U and fˆ by regarding
the contracted vertex set as a single vertex.
This algorithm is summarized in Figure 3.
THEOREM 4.3. Algorithm SPM is a strongly polynomial algorithm that performs O(n 7 log n) function evaluations and arithmetic operations.
PROOF. Each time we call the procedure Fix, the algorithm adds a new arc to D
or deletes a set of vertices. This can happen at most O(n 2 ) times. Each call to Fix
takes O(log n) phases. By Lemma 3.4, each phase after the first phase has O(n 2 )augmentations.
To bound the number of augmentations in the first phase, recall that the choiceof η implies that y(v) ≤ η for any extreme base y ∈ B( fˆ ) consistent with D. By
submodularity of fˆ , any extreme base y ∈ B( fˆ u ) consistent with Du satisfies y(t) ≤fˆ u (R(t)) − fˆ u (R(t)\{t}) ≤ fˆ (R(t)) − fˆ (R(t)\{t}) ≤ η for each t ∈ U \R(u).
Thus, for Fix( fˆ , D, η) or Fix( fˆ u , Du , η), we have y + (V ) ≤ nη. Since the numberof augmentations in a δ-phase is bounded by y + (U )/δ, the number of augmentationsin the first phase of any call to Fix is bounded by n.
Since the proof of Theorem 3.7 shows that the number of arithmetic operations
and function evaluations per augmentation is O(n 3 ), this yields an O(n 7 log n)bound on the total number of steps.
When applied to rational-valued submodular functions, SPM works in the spaceof polynomial size. In particular, as noted earlier, the encoding length of the numbers
generated in the Gaussian elimination is bounded by a polynomial in the input size

774

S. IWATA ET AL.

FIG. 3. A strongly polynomial algorithm for submodular function minimization.

(including the maximum encoding length of the function values) [Edmonds 1967],
and so is the size of the resulting multipliers λ. Thus, SPM is a strongly polynomialalgorithm.
5. Removing Gaussian Elimination
The algorithms described in Sections 3 and 4 both employ Gaussian elimination to
get a representation of x as a convex combination of a small number of extreme
bases. This step is, however, not necessary to obtain the polynomiality. We explain
here the effect of removing this step.
The size of the set I in the convex combination representation of x increases byat most n − 1 per augmentation, due to Lemma 3.5. The number of augmentations
per scaling phase is not affected by the size of I (see the proof of Lemma 3.4),
and hence remains O(n 2 ). Thus, the total number of bases introduced during thealgorithm is bounded by n times the number of augmentations. For the scaling
algorithm SFM( f ) described in Section 3, this is O(n 3 log M).
The size of I does affect the work per augmentation, however. In particular, it affects the number of calls to Double-Exchange during the search forMinimizing Submodular Functions775

an augmentation. In the proof of Lemma 3.6, it is explained that the numberof Double-Exchange operations before augmentation per extreme base in I
is at most n 2 . Thus, the total work per augmentation in the algorithm without
Reduce is O(n 5 log M). Thus, the number of arithmetic operations and function
evaluations used by this more combinatorial version of SFM( f ) is bounded byO(n 7 log2 M).
The strongly polynomial algorithm SPM( f ) described in Section 4 does notdepend on reducing the size of I for strong polynomiality. If this step is omitted,
the number of extreme bases in I may grow to O(n 3 log n) in an iteration of Fix.
Since each call to Fix starts with a single extreme base, the size of I will remainbounded throughout SPM( f ) by O(n 3 log n). This will increase the the work peraugmentation to O(n 5 log n). Thus, an overall bound on the number of steps isO(n 9 log2 n).
In contrast, if the linear algebraic step were omitted in the strongly polynomialalgorithm described in Schrijver [2000], the size of I could become exponential
in n.

6. Conclusion
This paper has presented a strongly polynomial algorithm for minimizing submodular functions defined on Boolean lattices: all subsets of the ground set V . Several
related problems have been shown to require algorithms for minimizing submodular functions on restricted families of subsets [Goemans and Ramakrishnan 1995;
Grötschel et al. 1988]. These problems have combinatorial solutions modulo an oracle for submodular function minimization on distributive lattices. Our algorithms
can be extended to minimize submodular functions defined on distributive lattices.
Consider a submodular function f: D → R defined on a distributive lattice D
represented by a poset P on V . Then, the associated base polyhedron is unboundedin general.
An easy way to minimize such a function f is to consider the reduction of f bya sufficiently large vector. As described in [Fujishige 1991, p. 56], we can compute an upper-bound M̂ on | f (X )| among X ∈ D. Let fˆ be the rank function of
the reduction by a vector with each component being equal to M̂. The submodular function fˆ is defined on 2V and the set of minimizers of fˆ coincides withthat of f . Thus, we may apply our algorithms. However, each evaluation of thefunction value of fˆ requires O(n 2 ) elementary operations in addition to a single
call for the evaluation of f . Schrijver [2000] describes a similar method to solve
this problem.
Alternatively, we can slightly extend the algorithms in Sections 3 and 4 by keeping
the base x ∈ B( f ) as a convex combination of extreme bases yi ’s plus a vector in
the characteristic cone of B( f ). The latter can be represented as a boundary of anonnegative flow in the Hasse diagram of P. This extension enables us to minimize
f in O(n 5 min{log n M̂, n 2 log n}) time, where M̂ is an upper bound on | f (X )|among X ∈ D.
Submodular functions defined on modular lattices naturally arise in linear algebra. Minimization of such functions has a significant application to canonical formsof partitioned matrices [Ito et al. 1994; Iwata and Murota 1995]. It remains an interesting open problem to develop an efficient algorithm for minimizing submodular

776

S. IWATA ET AL.

functions on modular lattices, even for those specific functions that arise frompartitioned matrices.
ACKNOWLEDGMENTS. We are grateful to Bill Cunningham, Michel Goemans, andMaiko Shigeno for their useful comments.

REFERENCESBIXBY, R. E., CUNNINGHAM, W. H., AND TOPKIS, D. M. 1985. Partial order of a polymatroid extreme
point. Math. Oper. Res. 10, 367–378.
CUNNINGHAM, W. H. 1984. Testing membership in matroid polyhedra. J. Combinat. Theory B36, 161–
188.
CUNNINGHAM, W. H. 1985. On submodular function minimization. Combinatorica 5, 185–192.
CUNNINGHAM, W. H., AND FRANK, A. 1985. A primal-dual algorithm for submodular flows. Math. Oper.
Res. 10, 251–262.
EDMONDS, J. 1967. Systems of distinct representatives and linear algebra. J. Res. NBS 71B, 241–245.
EDMONDS, J. 1970. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures
and Their Applications. R. Guy, H. Hanani, N. Sauer, and J. Schönheim, Eds. Gordon and Breach, pp.
69–87.
EDMONDS, J., AND GILES, R. 1977. A min-max relation for submodular functions on graphs. Ann. Discrete
Math. 1, 185–204.
EDMONDS, J., AND KARP, R. 1972. Theoretical improvements in algorithmic efficiency for network flow
problems. J. ACM 19, 2 (Apr.), 248–264.
ERVOLINA, T. R., AND MCCORMICK, S. T. 1993. Two strongly polynomial cut canceling algorithms forminimum cost network flow. Disc. Appl. Math. 46, 13–165.
FLEISCHER, L., AND IWATA, S. 2000. Improved algorithms for submodular function minimization andsubmodular flow. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland,Ore., May 21–23). ACM, New York, pp. 107–116.
FLEISCHER, L., IWATA, S., AND MCCORMICK, S. T. 2001. A faster capacity scaling algorithm for submodular flow. Math. Prog., to appear.
FRANK, A. 1982. An algorithm for submodular functions on graphs. Ann. Discrete Math. 16, 189–212.
FRANK, A., AND TARDOS, É. 1987. An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65.
FRANK, A., AND TARDOS, É. 1988. Generalized polymatroids and submodular flows. Math. Prog. 42,
489–563.
FRANK, A., AND TARDOS, É. 1989. An application of submodular flows. Linear Alg. Appl. 114/115,
329–348.
FUJISHIGE, S. 1978. Polymatroidal dependence structure of a set of random variables. Inf. Contr. 39,
55–72.
FUJISHIGE, S. 1980. Lexicographically optimal base of a polymatroid with respect to a weight vector.
Math. Oper. Res. 5, 186–196.
FUJISHIGE, S. 1984a. Submodular systems and related topics. Math. Prog. Study 22, 113–131.
FUJISHIGE, S. 1984b. Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions. Math. Prog. 29, 142–155.
FUJISHIGE, S. 1991. Submodular Functions and Optimization. North-Holland, Amsterdam, The Netherlands.
FUJISHIGE, S., AND IWATA, S. 2000. Algorithms for submodular flows. IEICE Trans. Inform. Syst. E83-D,
322–329.
GOEMANS, M. X., AND RAMAKRISHNAN, V. S. 1995. Minimizing submodular functions over families ofsubsets. Combinatorica 15, 499–513.
GRÖTSCHEL, M., LOVÁSZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its consequences incombinatorial optimization. Combinatorica 1, 169–197.
GRÖTSCHEL, M., LOVÁSZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.
HAN, T.-S. 1979. The capacity region of general multiple-access channel with correlated sources. Inf.
Cont. 40, 37–60.
HOPPE, B., AND TARDOS, É. 2000. The quickest transshipment problem. Math. Oper. Res. 25, 36–62.

Minimizing Submodular Functions

777

ITO, H., IWATA, S., AND MUROTA, K. 1994. Block-triangularization of partitioned matrices under similarity/equivalence transformations. SIAM J. Matrix Anal. Appl. 15, 1226–1255.
IWATA, S. 1997. A capacity scaling algorithm for convex cost submodular flows. Math. Prog. 76, 299–
308.
IWATA, S. 2001. A fully combinatorial algorithm for submodular function minimization. J. Combinat.
Theory, in press.
IWATA, S., MCCORMICK, S. T., AND SHIGENO, M. 1999. A strongly polynomial cut canceling algorithm
for the submodular flow problem. In Proceedings of the 7th MPS Conference on Integer Programmingand Combinatorial Optimization. Springer-Verlag, Berlin, Germany, pp. 259–272.
IWATA, S., AND MUROTA, K. 1995. A minimax theorem and a Dulmage-Mendelsohn type decomposition
for a class of generic partitioned matrices. SIAM J. Matrix Anal. Appl. 16, 719–734.
LOVÁSZ, L. 1983. Submodular functions and convexity. In Mathematical Programming—The State of
the Art, A. Bachem, M. Grötschel and B. Korte, Eds. Springer-Verlag, New York, pp. 235–257.
NAGAMOCHI, H., AND IBARAKI, T. 1992. Computing edge-connectivity in multigraphs and capacitatedgraphs. SIAM J. Disc. Math. 5, 54–64.
NARAYANAN, H. 1995. A rounding technique for the polymatroid membership problem. Linear Alg.
Appl. 221, 41–57.
QUEYRANNE, M. 1998. Minimizing symmetric submodular functions. Math. Prog. 82, 3–12.
SCHRIJVER, A. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combinat. Theory B80, 346–355.
SHAPLEY, L. S. 1971. Cores of convex games. Int. J. Game Theory 1, 11–26.
SOHONI, M. A. 1992. Membership in submodular and other polyhedra. Tech. Rep. TR-102-92. Dept.
Comput. Sci. Eng., Indian Institute of Technology, Bombay, India.
TAMIR, A. 1993. A unifying location model on tree graphs based on submodularity properties. Disc.
Appl. Math. 47, 275–283.
TARDOS, É. 1985. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247–
255.
RECEIVED JULY 1999; REVISED JANUARY 2001; ACCEPTED JANUARY 2001

Journal of the ACM, Vol. 48, No. 4, July 2001.