SIAM J. DISCRETE MATH.
Vol. 19, No. 4, pp. 1065–1073

c 2006 Society for Industrial and Applied Mathematics


BISUBMODULAR FUNCTION MINIMIZATION∗SATORU FUJISHIGE† AND SATORU IWATA‡
Abstract. This paper presents the ﬁrst combinatorial polynomial algorithm for minimizing
bisubmodular functions, extending the scaling algorithm for submodular function minimization due
to Iwata, Fleischer, and Fujishige. Since the rank functions of delta-matroids are bisubmodular,
the scaling algorithm naturally leads to the ﬁrst combinatorial polynomial algorithm for testing
membership in delta-matroid polyhedra.
Key words. bisubmodular function, delta-matroid, scaling algorithm
AMS subject classiﬁcation. 90C27
DOI. 10.1137/S0895480103426339

1. Introduction. Let V be a ﬁnite nonempty set of cardinality n and 3V denotethe set of ordered pairs of disjoint subsets of V . Two binary operations  and  on
3V are deﬁned by(X1 , Y1 )  (X2 , Y2 ) = ((X1 ∪ X2 )\(Y1 ∪ Y2 ), (Y1 ∪ Y2 )\(X1 ∪ X2 )),(X1 , Y1 )  (X2 , Y2 ) = (X1 ∩ X2 , Y1 ∩ Y2 ).
A function f : 3V → R is called bisubmodular if it satisﬁes
f (X1 , Y1 ) + f (X2 , Y2 ) ≥ f ((X1 , Y1 )  (X2 , Y2 )) + f ((X1 , Y1 )  (X2 , Y2 ))for any (X1 , Y1 ) and (X2 , Y2 ) in 3V . This paper presents the ﬁrst combinatorial
polynomial algorithm for minimizing bisubmodular functions.
Examples of bisubmodular functions include the rank functions of delta-matroids
introduced independently by Bouchet [3] and Chandrasekaran–Kabadi [6]. A deltamatroid is a set system (V, F) with F being a nonempty family of subsets of V thatsatisﬁes the following exchange property:∀F1 , F2 ∈ F, ∀v ∈ F1 F2 , ∃u ∈ F1 F2 : F1 {u, v} ∈ F,
wheredenotes the symmetric diﬀerence. A slightly restricted set system with anadditional condition ∅ ∈ F had been introduced by Dress–Havel [11]. A member of F
is called a feasible set of the delta-matroid. Note that the base and the independentset families of a matroid satisfy this exchange property. Thus, a delta-matroid is a
generalization of a matroid.
Chandrasekaran–Kabadi [6] showed that the rank function  : 3V → Z deﬁned by
(X, Y ) = max{|X ∩ F | − |Y ∩ F | | F ∈ F}
∗ Received by the editors April 25, 2003; accepted for publication (in revised form) September
22, 2005; published electronically February 3, 2006. A preliminary version of this paper appearedin Proceedings of the Eighth Conference on Integer Programming and Combinatorial Optimization,
LNCS 2081, Springer-Verlag, Berlin, 2001, pp. 160–169.
http://www.siam.org/journals/sidma/19-4/42633.html† Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan (fujishig@kurims.kyoto-u.ac.jp).
‡ Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan (iwata@mist.i.u-tokyo.ac.jp).

1065

1066

SATORU FUJISHIGE AND SATORU IWATA

is bisubmodular. The convex hull of the characteristic vectors of the feasible sets is
described byP() = {x | x ∈ RV , ∀(X, Y ) ∈ 3V : x(X) − x(Y ) ≤ (X, Y )},which is called the delta-matroid polyhedron. This fact follows from the greedy algorithm [3, 6] for optimizing a linear function over the feasible sets.
Given a vector x ∈ RV , one can test if x belongs to P() by minimizing abisubmodular function f (X, Y ) = (X, Y ) − x(X) + x(Y ). Even for such a special
case of bisubmodular function minimization, no combinatorial algorithm was known
to run in polynomial time. This is in contrast with the matroid polyhedron, for which
Cunningham [7] devised a combinatorial strongly polynomial algorithm for testing
membership.
A simple example of a delta-matroid is a matching delta-matroid [4], whose feasible sets are the perfectly matchable vertex subsets of an undirected graph. The
corresponding delta-matroid polyhedron is the matchable set polytope [2]. For thisspecial case, Cunningham–Green-Krótki [10] developed an augmenting path algorithm
for solving the separation problem in polynomial time with the aid of the scaling technique.
A bisubmodular function also generalizes a submodular (set) function. Let 2V
denote the family of all the subsets of V . A function g : 2V → R is called submodular
if it satisﬁesg(Z1 ) + g(Z2 ) ≥ g(Z1 ∪ Z2 ) + g(Z1 ∩ Z2 )for any Z1 , Z2 ⊆ V . For a submodular function g, we deﬁne a bisubmodular function
f : 3V → R by
f (X, Y ) = g(X) + g(V \Y ) − g(V ).
If (X, Y ) is a minimizer of f , then both X and V \Y are minimizers of g. Thus, bisubmodular function minimization (BSFM) is a generalization of submodular function
minimization.
The ﬁrst polynomial algorithm for submodular function minimization is given byGrötschel–Lovász–Schrijver [16]. They also give the ﬁrst strongly polynomial algorithms in [17]. Their algorithms rely on the ellipsoid method, which is not eﬃcientin practice. Two combinatorial strongly polynomial algorithms have been devised
independently by Schrijver [23] and Iwata–Fleischer–Fujishige [18]. Both of these
new algorithms are based on the combinatorial pseudopolynomial algorithm given by
Cunningham [8]. The algorithm of Schrijver [23] directly achieves a strongly polynomial bound, whereas Iwata–Fleischer–Fujishige [18] develop a scaling algorithm withweakly polynomial time complexity and then convert it to a strongly polynomial one.
In the present paper, we extend the scaling algorithm of Iwata–Fleischer–Fujishige[18] to solve the minimization problem for integer-valued bisubmodular functions.
The resulting algorithm runs in O(n5 log M ) time, where M designates the maximum
value of f . This bound is weakly polynomial. A strongly polynomial version will bepresented in a forthcoming paper by McCormick–Fujishige [21].
As a generalization of the delta-matroid polyhedron, a bisubmodular polyhedronP(f ) = {x | x ∈ RV , ∀(X, Y ) ∈ 3V : x(X) − x(Y ) ≤ f (X, Y )}is associated with a general bisubmodular function f : 3V → R, where we assume
f (∅, ∅) = 0. The linear optimization problem over the bisubmodular polyhedron can

BISUBMODULAR FUNCTION MINIMIZATION

1067

be solved by the greedy algorithm of Dunstan–Welsh [12]. Based on the validity of thisgreedy algorithm, Qi [22] established a connection between bisubmodular functions
and their convex extensions. This generalizes a result of Lovász [19] on submodular
functions. Qi [22] also mentioned that the connection provides a polynomial algorithm
for bisubmodular function minimization using the ellipsoid method. In contrast, our
combinatorial algorithm directly deals with the separation problem for bisubmodular
polyhedra.
The concept of delta-matroid is extended to that of jump system by Bouchet–Cunningham [5]. A jump system is a set of lattice points satisfying a certain axiom.
Examples include the set of degree sequences of a graph [9]. Lovász [20] investigatedthe membership problem in jump systems and proved a min-max theorem for a fairly
wide class of jump systems. The lattice points contained in an integral bisubmodular
polyhedron form a jump system, called a convex jump system, and conversely theconvex hull of a jump system is an integral bisubmodular polyhedron. An example ofa convex jump system is the so-called b-matching degree sequence polyhedron [9]. Avery recent paper of Zhang [24] presented an augmenting path separation algorithm
for this polyhedron. The present paper provides a more general algorithmic approachto the membership problem in convex jump systems.
2. Bisubmodular polyhedra. This section provides a preliminary on bisubmodular polyhedra. See [14, section 3.5 (b)] for more detail and background.

For any vector y ∈ RV , we denote y = v∈V |y(v)|. Concerning the shortest distance from a given vector x◦ to the bisubmodular polyhedron P(f ), we havethe following min-max relation, which is essentially equivalent to an earlier result of
Cunningham–Green-Krótki [9].
Theorem 2.1 (Fujishige [15]). For any bisubmodular function f : 3V → R andany vector x◦ ∈ RV ,min{x − x◦  | x ∈ P(f )} = max{x◦ (X) − x◦ (Y ) − f (X, Y ) | (X, Y ) ∈ 3V }holds. Moreover, if f and x◦ are integer valued, then there is an integral vector x thatattains the minimum in the left-hand side.
When x◦ = 0, the min-max relation characterizes the minimum value of f . Our
combinatorial algorithm is built on this characterization.
We now turn to the greedy algorithm for computing an extreme point of a bisubmodular polyhedron. See also [1] for related structural results on extreme points ofbisubmodular polyhedra.
Let σ : V → {+, −} be a sign function. For any subset U ⊆ V , we denote by
U |σ the pair (X, Y ) ∈ 3V with X = {u | u ∈ U, σ(u) = +} and Y = {u | u ∈U, σ(u) = −}. We also write f (U |σ) = f (X, Y ) for any function f : 3V → R, andx(U |σ) = x(X) − x(Y ) for any vector x ∈ RV .
Let L = (v1 , · · · , vn ) be a linear ordering of V . For each j = 1, . . . , n, let L(vj ) ={v1 , . . . , vj }. The greedy algorithm with respect to L and a sign function σ assigns
y(v) := σ(v){f (L(v)|σ) − f (L(v)\{v}|σ)} for each v ∈ V . Then the resulting vectory ∈ RV is an extreme point of the bisubmodular polyhedron P(f ).
Given a weight function w : V → R, construct a linear ordering L = (v1 , . . . , vn )and a sign function σ that satisﬁes |w(v1 )| ≥ · · · ≥ |w(vn )| and w(v) = σ(v)|w(v)|for each v ∈ V . Then the vector y generatedby the greedy algorithm with respect
to L and σ maximizes the linear functionv∈V w(v)y(v) over the bisubmodular
polyhedron P(f ).

1068

SATORU FUJISHIGE AND SATORU IWATA

3. Scaling algorithm. This section presents a scaling algorithm for minimizing
an integer-valued bisubmodular function f : 3V → Z, provided that an oracle for
evaluating the function value is available.
The scaling algorithm works with a positive parameter δ. The algorithm keeps avector x ∈ P(f ) as a convex combination of extreme points of P(f) indexed by ﬁnite
set I. Namely, x = i∈I λi yi with λi > 0 for each i ∈ I and i∈I λi = 1. Eachextreme point yi is generated by the greedy algorithm with respect to Li and σi . It
also keeps a pair of functions ϕ : V × V → R and ψ : V × V → R. The function ϕis skew-symmetric, i.e., ϕ(u, v) + ϕ(v, u) = 0 for any u, v ∈ V , while ψ is symmetric,i.e., ψ(u, v) = ψ(v, u) for any u, v ∈ V . These functions are called δ-feasible if theysatisfy −δ ≤ ϕ(u, v) ≤ δ and −δ≤ ψ(u, v) ≤ δ for any u, v ∈ V . The boundaries ∂ϕand ∂ψ are deﬁned by ∂ϕ(u) = v∈V ϕ(u, v) and ∂ψ(u) = v∈V ψ(u, v).
The algorithm starts with an extreme point x ∈ P(f ) generated by the greedy
algorithm with respect to a linear ordering L and a sign function σ. The initial valueof δ is given by δ := x/n2 , and the initial values of ϕ and ψ are zero.
Each scaling phase starts by cutting the value of δ in half. Then it modiﬁes ϕand ψ to make them δ-feasible. This can be done by setting each ϕ(u, v) and ψ(u, v)
to the closest values in the interval [−δ, δ].
The rest of the scaling phase aims at decreasing z for z = x + ∂ϕ + ∂ψ. It
uses three procedures: Augment, Double-Exchange, and Tail-Exchange. Procedure
Augment decreases z by δ, whereas Double-Exchange and Tail-Exchange modify x,
ϕ, ψ keeping z invariant. The scaling phase terminates when none of these procedures
are applicable. Then z is shown to be small enough to keep moderate the number
of applications of Augment in the next scaling phase. Furthermore, if δ < 1/3n2 , thenthe algorithm detects a pair (X, Y ) that minimizes f .
Given δ-feasible ϕ and ψ, the algorithm constructs an auxiliary directed graph
G(ϕ, ψ) as follows. Let V + and V − be two copies of V . For each v ∈ V , we denoteits copies by v + ∈ V + and v − ∈ V − . The vertex set of G(ϕ, ψ) is V + ∪ V − . For
any subset U ⊆ V , deﬁne U + = {u+ | u ∈ U } and U − = {u− | u ∈ U }. The arc setA(ϕ, ψ) = A(ϕ) ∪ A(ψ) of G(ϕ, ψ) is deﬁned byA(ϕ) = {(u+ , v + ) | u = v, ϕ(u, v) ≤ 0} ∪ {(u− , v − ) | u = v, ϕ(u, v) ≥ 0},
A(ψ) = {(u+ , v − ) | ψ(u, v) ≤ 0} ∪ {(u− , v + ) | ψ(u, v) ≥ 0}.
Note that, for any u, v ∈ V and any sign function η on V , the graph G(ϕ, ψ) has
a directed path from uη(u) to v η(v) if and only if G(ϕ, ψ) has a directed path fromv −η(v) to u−η(u) .
Let S = {v | v ∈ V, z(v) ≤ −δ} and T = {v | v ∈ V, z(v) ≥ δ}. A simple directed
path in G(ϕ, ψ) from S + ∪ T − to S − ∪ T + is called a δ-augmenting path. If there
exists a δ-augmenting path P , the algorithm applies the following δ-augmentation to
ϕ and ψ.
Augment(δ, P, ϕ, ψ):• For each (u+ , v + ) in P , ϕ(u, v) := ϕ(u, v) + δ/2 and ϕ(v, u) := ϕ(v, u) − δ/2.
• For each (u− , v − ) in P , ϕ(u, v) := ϕ(u, v) − δ/2 and ϕ(v, u) := ϕ(v, u) + δ/2.
• For each (u+ , v − ) in P , ψ(u, v) := ψ(u, v) + δ/2 and ψ(v, u) := ψ(v, u) + δ/2.
• For each (u− , v + ) in P , ψ(u, v) := ψ(u, v) − δ/2 and ψ(v, u) := ψ(v, u) − δ/2.
Note that a δ-augmentation does not change x, maintains δ-feasibility, and decreases
z by δ.
After each δ-augmentation, the algorithm computes an expression of x as a convex
combination of aﬃnely independent extreme points of P(f ) chosen from among {yi |BISUBMODULAR FUNCTION MINIMIZATION

1069

Double-Exchange(i, u, v);
β := f (Li (u)\{v}|σi ) − f (Li (u)|σi ) + σi (v)yi (v);α := min{δ, λi β};
If α < λi β thenk ← a new index;
I := I ∪ {k};λk := λi − α/β;λi := α/β;yk := yi ;Lk := Li ;Update Li by interchanging u and v;
yi := yi + β(σi (u)χu − σi (v)χv );x := x + α(σi (u)χu − σi (v)χv );If σi (u) = σi (v) thenϕ(u, v) := ϕ(u, v) − σi (u)α;ϕ(v, u) := ϕ(v, u) + σi (u)α;Elseψ(u, v) := ψ(u, v) − σi (u)α;ψ(v, u) := ψ(v, u) − σi (u)α.
Fig. 3.1. Algorithmic description of Procedure Double-Exchange(i, u, v).

i ∈ I}. This can be done by a standard linear programming technique using Gaussianelimination.
If there is no δ-augmenting path, let X + ⊆ V + and Y − ⊆ V − be the sets ofvertices reachable by directed paths from S + ∪ T − . Then we have S ⊆ X, T ⊆ Y ,and X ∩ Y = ∅. For each i ∈ I, consider a pair of disjoint subsets Wi = {u | uσi (u) ∈X + ∪ Y − } and Ri = {u | uσi (u) ∈ X − ∪ Y + }. Note that Wi ∪ Ri = X ∪ Y . We now
introduce two procedures: Double-Exchange and Tail-Exchange.
Procedure Double-Exchange(i, u, v) is applicable if u immediately succeeds v in Li
and either u ∈ Wi and v ∈/ Wi or u ∈/ Ri and v ∈ Ri hold. Such a triple (i, u, v) iscalled active. The ﬁrst step of the procedure is to compute
β := f (Li (u)\{v}|σi ) − f (Li (u)|σi ) + σi (v)yi (v).
Then it interchanges u and v in Li and updates yi as yi := yi + β(σi (u)χu − σi (v)χv ).
The resulting yi is an extreme point generated by the new linear ordering Li and signfunction σi .
If λi β ≤ δ, Double-Exchange(i, u, v) is called saturating. Otherwise, it is called
nonsaturating. In the nonsaturating case, the procedure adds to I a new index kwith yk , σk and Lk being the previous yi , σi and Li , and assigns λk := λi − δ/βand λi := δ/β. In both cases, x moves to x := x + α(σi (u)χu − σi (v)χv ) with
α = min{δ, λi β}. In order to keep z invariant, the procedure ﬁnally modiﬁes ϕ or ψ
appropriately. If σi (u) = σi (v), it updates ϕ(u, v) := ϕ(u, v) − σi (u)α and ϕ(v, u) :=ϕ(v, u) + σi (u)α. On the other hand, if σi (u) = σi (v), then ψ(u, v) := ψ(u, v) − σi (u)αand ψ(v, u) := ψ(v, u) − σi (u)α. A formal description of Double-Exchange is given in
Figure 3.1.
Lemma 3.1. As a result of nonsaturating Double-Exchange(i, u, v), a new vertex
joins X ∪ Y or a δ-augmenting path appears in G(ϕ, ψ).

1070

SATORU FUJISHIGE AND SATORU IWATA

Tail-Exchange(i, v);
σi (v) := −σi (v);β := f (V |σi ) − f (V \{v}|σi ) − σi (v)yi (v);α := min{δ, λi β};
If α < λi β thenk ← a new index;
I := I ∪ {k};λk := λi − α/β;λi := α/β;yk := yi ;Lk := Li ;yi := yi + σi (v)βχv ;x := x + σi (v)αχv ;ψ(v, v) := ψ(v, v) − σi (v)α.
Fig. 3.2. Algorithmic description of Procedure Tail-Exchange(i, v).

Proof. The nonsaturating Double-Exchange(i, u, v) updates ϕ or ψ so that a newarc (uσi (u) , v σi (v) ) should appear in G(ϕ, ψ). Recall that either u ∈ Wi and v ∈/ Wior u ∈/ Ri and v ∈ Ri holds. If u ∈ Wi and v ∈/ Ri ∪ Wi , the new arc makes v σi (v)reachable from S + ∪ T − . If v ∈ Ri and u ∈/ Wi ∪ Ri , the new arc makes uσi (u)reachable to S − ∪ T + . Thus, in these cases, a new vertex v or u is added to X ∪ Y .
Finally, if u ∈ Wi and v ∈ Ri , the new arc yields a δ-augmenting path.
Procedure Tail-Exchange(i, v) is applicable if v is the last element in Li and v ∈ Ri .
Such a pair (i, v) is also called active. The ﬁrst step of the procedure is to reverse thesign σi (v). It then computes
β := f (V |σi ) − f (V \{v}|σi ) − σi (v)yi (v)and updates yi := yi + σi (v)βχv . The resulting yi is an extreme point generated by
Li and the new σi .
If λi β ≤ δ, Tail-Exchange(i, v) is called saturating. Otherwise, it is called nonsaturating. In the nonsaturating case, the procedure adds to I a new index k with yk , σkand Lk being the previous yi , σi and Li , and assigns λk := λi − δ/β and λi := δ/β.
In both cases, x moves to x := x + σi (v)αχv with α = min{δ, λi β}. In order to keepz invariant, the procedure ﬁnally modiﬁes ψ as ψ(v, v) := ψ(v, v) − σi (v)α. A formal
description of Tail-Exchange is given in Figure 3.2.
Lemma 3.2. As a result of nonsaturating Tail-Exchange(i, v), a δ-augmenting
path appears in G(ϕ, ψ).
Proof. Suppose the algorithm applies Tail-Exchange(i, v) with σi (v) = τ . Thenv −τ is reachable from S + ∪ T − and v τ is reachable to S − ∪ T + in G(ϕ, ψ). The
nonsaturating Tail-Exchange(i, v) changes σi (v) to −τ and updates ψ(v, v) so that a
new arc (v −τ , v τ ) appears in G(ϕ, ψ), which yields a δ-augmenting path from S + ∪T −to S − ∪ T + .
If there is no δ-augmenting path and neither Double-Exchange nor Tail-Exchange
is applicable, the algorithm terminates the scaling phase. Then it goes to the next
scaling phase unless δ < 1/3n2 . If δ < 1/3n2 , the algorithm terminates by returning
the current (X, Y ) as a minimizer of f .
A formal description of our scaling algorithm BSFM is now given in Figure 3.3.

BISUBMODULAR FUNCTION MINIMIZATION

1071

BSFM(f ):Initialization:
L ← a linear ordering on V ;σ ← a sign function on V ;x ← an extreme vector in P(f ) generated by L and σ;
I := {}, y := x, λ := 1, L := L;
ϕ := 0, ψ := 0;δ ← x/n2 ;While δ ≥ 1/3n2 doδ := δ/2;
For (u, v) ∈ V × V do
Change ϕ(u, v) and ψ(u, v) to the closest values in the interval [−δ, δ];S := {v | x(v) + ∂ϕ(v) + ∂ψ(v) ≤ −δ};T := {v | x(v) + ∂ϕ(v) + ∂ψ(v) ≥ δ};
X + ← the set of vertices in V + reachable from S + ∪ T − in G(ϕ, ψ);Y − ← the set of vertices in V − reachable from S + ∪ T − in G(ϕ, ψ);Q ← the set of active triples and active pairs;
While ∃δ-augmenting path or Q = ∅ do
If ∃P : δ-augmenting path thenAugment(δ, P, ϕ, ψ);Update S, T , X + ,Y − , Q;
Express x as x = i∈I λi yi by possibly smaller aﬃnely independent
subset I and positive coeﬃcients λi > 0 for i ∈ I;
Else
While  ∃δ-augmenting path and Q = ∅ do
Find an active (i, u, v) ∈ Q or active (i, v) ∈ Q;
Apply Double-Exchange(i, u, v) or Tail-Exchange(i, v);
Update X + , Y − , Q;
Return (X, Y );End.
Fig. 3.3. A scaling algorithm for bisubmodular function minimization.

4. Validity and complexity. This section is devoted to the analysis of ourscaling algorithm. We ﬁrst discuss the validity.
Lemma 4.1. At the end of each scaling phase, the current (X, Y ) ∈ 3V andz = x + ∂ϕ + ∂ψ satisfy z ≤ 2nδ − f (X, Y ).
Proof. At the end of each scaling phase, we have yi (X) − yi (Y ) = f (X, Y )for each i ∈ I. Hence, x satisﬁes x(X) − x(Y ) = f (X, Y ). By the deﬁnition of(X, Y ), we have ϕ(u, v) > 0 for u ∈ X, v ∈ 
V \X and ϕ(u, v) < 0 for u ∈ Y ,v ∈ V \Y . These
inequalities
imply
∂ϕ(X)
=
{ϕ(u, v) | u ∈ X, v ∈ V \X} > 0and ∂ϕ(Y ) ={ϕ(u, v) | u ∈ Y, v ∈ V \Y } < 0. Similarly, we have ψ(u, v) > 0
for
Y , v ∈ V \X, which imply ∂ψ(X) = u ∈ X, v ∈ V \Y and ψ(u, v) < 0 for u ∈
{ψ(u,
v)
|
u
∈
X,
v
∈
V
}
>
θ
and
∂ψ(Y
)
=
{ψ(u, v) | u ∈ Y, v ∈ V } < θ, whereθ = {ψ(u, v) | u ∈ X, v ∈ Y }. Since S ⊆ X and T ⊆ Y , we have z(v) ≥ −δ forv ∈ V \X and z(v) ≤ δ for v ∈ V \Y . Therefore, we have z ≤ −z(X) + z(Y ) + 2nδ ≤−x(X) + x(Y ) + 2nδ = −f (X, Y ) + 2nδ.
Theorem 4.2. The algorithm obtains a minimizer of f at the end of the lastscaling phase.

1072

SATORU FUJISHIGE AND SATORU IWATA

Proof. Note that δ < 1/3n2 at the end of the last scaling phase. For each v ∈ V ,since |∂ϕ(v)| ≤ (n−1)δ and |∂ψ(v)| ≤ nδ, we have |x(v)| ≤ |z(v)|+|∂ϕ(v)|+|∂ψ(v)| ≤|z(v)| + (2n − 1)δ. Then it follows from Lemma 4.1 that x ≤ (2n2 + n)δ − f (X, Y ) <1 − f (X, Y ). For any (X  , Y  ) ∈ 3V , we have f (X  , Y  ) ≥ x(X  ) − x(Y  ) ≥ −x >f (X, Y ) − 1. Hence (X, Y ) is a minimizer of the integer-valued function f .
We now give a running time bound of our algorithm.
Lemma 4.3. Each scaling phase performs O(n2 ) augmentations.
Proof. At the beginning of each scaling phase, the algorithm modiﬁes ϕ and ψ tomake them δ-feasible (for the new δ). This changes z by at most 2n2 δ. Therefore,by Lemma 4.1, the pair (X, Y ) obtained at the end of the previous scaling phase mustsatisfy z ≤ 2n2 δ + 4nδ − f (X, Y ) after updating ϕ and ψ at the beginning of thecurrent scaling phase. On the other hand, at the end of the current scaling phase, wehave z ≥ −z(X) + z(Y ) ≥ −x(X) + x(Y ) − 2n2 δ ≥ −f (X, Y ) − 2n2 δ. Thus, during
the scaling phase, z decreases by at most 4nδ + 4n2 δ. Since each δ-augmentation
decreases z by δ, the number of δ-augmentations in the scaling phase is at most
4n2 + 4n, which is O(n2 ).
Lemma 4.4. The algorithm performs Procedure Double-Exchange O(n3 ) times
and Tail-Exchange O(n2 ) times between δ-augmentations.
Proof. In Double-Exchange, a vertex in Wi moves in Li ahead of some vertex
not in Wi and/or a vertex in Ri moves behind some vertex not in Ri . ProcedureTail-Exchange changes a vertex of Ri into Wi . No vertex goes out of Wi . A vertex of
Ri can be switched to Wi by Tail-Exchange. However, it does not go out of Ri ∪ Wi .
Thus, for each i ∈ I, after at most O(n2 ) applications of Double-Exchange and O(n)applications of Tail-Exchange to i ∈ I, the subset Ri is empty and Wi = Li (w) holds forsome w ∈ V . At this point, neither Double-Exchange nor Tail-Exchange is applicable
to i ∈ I.
 After each δ-augmentation, the algorithm updates the convex combination x =i∈I λi yi so that |I| ≤ n + 1. A new index is added to I as a result of nonsaturating
Double-Exchange(i, u, v) and Tail-Exchange(i, v). It follows from Lemmas 3.1 and 3.2that this can happen at most n − 1 times before the algorithm ﬁnds a δ-augmenting
path or ﬁnishes the scaling phase. Hence, |I| is always O(n), and the algorithm
performs Double-Exchange O(n3 ) times and Tail-Exchange O(n2 ) times between δaugmentations.
Let M be the maximum value of f . Since f (∅, ∅) = 0, the maximum value M isnonnegative.
Theorem 4.5. The scaling algorithm ﬁnds a minimizer of f in O(n5 log M )time.
Proof. For the initial x ∈ P(f ), let B = {v | x(v) > 0} and C = {v | x(v) < 0}.
Then we have x = x(B) − x(C) ≤ f (B, C) ≤ M . Hence the algorithm performs
O(log M ) scaling phases. It follows from Lemmas 4.3 and 4.4 that each scaling phase
performs O(n5 ) function evaluations and arithmetic operations. Therefore the total
running time is O(n5 log M ).
5. Conclusion. We have described a combinatorial polynomial algorithm forminimizing integer-valued bisubmodular functions. If we are given a positive lower
bound  for the diﬀerence between the minimum and the second minimum value of f ,a variant of the present algorithm works for any real-valued bisubmodular function f .
The only required modiﬁcation is to change the stopping rule δ < 1/3n2 to δ < /3n2 .
The running time is O(n5 log(M/)). Thus we obtain a polynomial algorithm fortesting membership in delta-matroid polyhedra.

BISUBMODULAR FUNCTION MINIMIZATION1073

One can make this algorithm strongly polynomial with the aid of the genericpreprocessing technique of Frank–Tardos [13] that uses the simultaneous Diophantine
approximation. However, a more natural strongly polynomial algorithm is desirable.
Subsequent to this paper, McCormick and Fujishige [21] have devised such an algorithm for general bisubmodular function minimization.
Acknowledgments. The authors are very grateful to Kazutoshi Ando and an
anonymous referee for pointing out errors in earlier versions of this manuscript.
REFERENCES[1] K. Ando and S. Fujishige, On structures of bisubmodular polyhedra, Math. Program., 74(1996), pp. 293–317.
[2] E. Balas and W. R. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary
graph, Combinatorica, 9 (1989), pp. 321–337.
[3] A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program., 38 (1987), pp. 147–
159.
[4] A. Bouchet, Matchings and -matroids, Discrete Appl. Math., 24 (1989), pp. 55–62.
[5] A. Bouchet and W. H. Cunningham, Delta-matroids, jump systems and bisubmodular polyhedra, SIAM J. Discrete Math., 8 (1995), pp. 17–32.
[6] R. Chandrasekaran and S. N. Kabadi, Pseudomatroids, Discrete Math., 71 (1988), pp. 205–
217.
[7] W. H. Cunningham, Testing membership in matroid polyhedra, J. Combin. Theory Ser. B, 36(1984), pp. 161–188.
[8] W. H. Cunningham, On submodular function minimization, Combinatorica, 5 (1985), pp. 185–
192.
[9] W. H. Cunningham and J. Green-Krótki, b-matching degree sequence polyhedra, Combinatorica, 11 (1991), pp. 219–230.
[10] W. H. Cunningham and J. Green-Krótki, A separation algorithm for the matchable set
polytope, Math. Programming, 65 (1994), pp. 139–150.
[11] A. Dress and T. F. Havel, Some combinatorial properties of discriminants in metric vector
spaces, Adv. Math., 62 (1986), pp. 285–312.
[12] F. D. J. Dunstan and D. J. A. Welsh, A greedy algorithm solving a certain class of linear
programmes, Math. Program., 5 (1973), pp. 338–353.
´ Tardos, An application of simultaneous Diophantine approximation in[13] A. Frank and E.
combinatorial optimization, Combinatorica, 7 (1987), pp. 49–65.
[14] S. Fujishige, Submodular Functions and Optimization, North-Holland, Amsterdam, 1991; 2nded., 2005.
[15] S. Fujishige, A min-max theorem for bisubmodular polyhedra, SIAM J. Discrete Math., 10(1997), pp. 294–308.
[16] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences incombinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.
[17] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial
Optimization, Springer-Verlag, Berlin, 1988.
[18] S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm forminimizing submodular functions, J. ACM, 48 (2001), pp. 761-777.
[19] L. Lovász, Submodular functions and convexity, in Mathematical Programming — The Stateof the Art, A. Bachem, M. Grötschel and B. Korte, eds., Springer-Verlag, Berlin, 1983,
pp. 235–257.
[20] L. Lovász, The membership problem in jump systems, J. Combin. Theory Ser. B, 70 (1997),
pp. 45–66.
[21] S. T. McCormick and S. Fujishige, Better algorithms for bisubmodular function minimization, manuscript, 2003.
[22] L. Qi, Directed submodularity, ditroids and directed submodular ﬂows, Math. Program., 42(1988), pp. 579–599.
[23] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B, 80 (2000), pp. 346–355.
[24] F. Zhang, A separation algorithm for b-matching degree-sequence polyhedra, Math. Oper. Res.,28 (2003), pp. 92–102.