Murota K. Matrices and Matroids for Systems Analysis

Подождите немного. Документ загружается.

302 5. Polynomial Matrix and Valuated Matroid

In the upper-bound lemma it is natural to ask for a (suﬃcient) condition

under which the bound (5.46) is tight. Comparison of the unique-matching

lemma (Lemma 2.3.18) and the upper-bound lemma will suggest

[Unique-max condition]

There exists exactly one maximum-weight perfect matching in G(B,B



In what follows we shall show (in Lemma 5.2.35 below) that this is indeed a

suﬃcient condition for the tightness in (5.46).

First we note the following fact, rephrasing the unique-max condition in

terms of “potential” or “dual variable”.

Lemma 5.2.32. Let B ∈Band B



⊆ V with |B



\ B| = |B \B



| = m.

(1) G(B, B



) has a perfect matching if and only if there exist 6p :(B \



) ∪(B



\B) → R and indexings of the elements of B \B



and B



\B,say

B \ B



= {u

, ···,u

} and B



\ B = {v

, ···,v

}, such that

ω(B,u

) − 6p(u

)+6p(v

)



=0(1≤ i = j ≤ m)

≤ 0(1≤ i, j ≤ m).

(5.47)

Then, 6ω(B,B





i=1

6p(u

) −



j=1

6p(v

(2) The pair (B, B



) satisﬁes the unique-max condition if and only if there

exist 6p :(B \B



) ∪(B



\B) → R and indexings of the elements of B \B



and



\ B,sayB \ B



= {u

, ···,u

} and B



\ B = {v

, ···,v

}, such that

ω(B,u

) − 6p(u

)+6p(v

)

⎧

⎨

⎩

=0(1≤ i = j ≤ m)

≤ 0(1≤ j<i≤ m)

< 0(1≤ i<j≤ m).

(5.48)

Proof. This follows from Theorem 2.2.36.

Lemma 5.2.33. Let B ∈Band u, u

◦

,v,v

◦

be four distinct elements with

{u, u

◦

}⊆B, {v,v

◦

}⊆V \ B,andletB



= B −{u, u

◦

} + {v, v

◦

}. Assume

that M = {(u, v), (u

◦

)} is the unique maximum-weight perfect matching

in G(B,B



(1) B



∈Band ω(B



)=ω(B)+6ω(B, B



(2) For B

◦

= B − u

◦

+ v

◦

we have

ω(B

◦

,u,v)=ω(B, u,v),

ω(B

◦

,u,u

◦

)=ω(B,u,v

◦

) − ω(B, u

◦

ω(B

◦

,v)=ω(B,u

◦

,v) − ω(B, u

◦

Proof. (1) Putting B

∗

= B − u + v we see

ω(B

∗

)+ω(B

◦

)=ω(B,u,v)+ω(B, u

◦

)+2ω(B)=6ω(B, B



)+2ω(B).

(5.49)

By applying the exchange axiom (5.14) to (B

◦

∗

) with u ∈ B

◦

∗

we have

5.2 Valuated Matroid 303

ω(B

∗

)+ω(B

◦

) ≤ ω(B

∗

− v



+ u)+ω(B

◦

+ v



− u)

for some v



∈ B

∗

\ B

◦

= {u

◦

,v}. Combining this with (5.49) we obtain

6ω(B, B



)+2ω(B) ≤ ω(B

∗

− v



+ u)+ω(B

◦

+ v



− u). (5.50)

Suppose that v



= u

◦

. Then

RHS of (5.50) = ω(B

∗

− u

◦

+ u)+ω(B

◦

+ u

◦

− u)

= ω(B −u

◦

+ v)+ω(B − u + v

◦

)

= ω(B, u

◦

,v)+ω(B,u, v

◦

)+2ω(B).

This means that M



= {(u

◦

,v), (u, v

◦

)} is also a maximum-weight perfect

matching in G(B, B



), a contradiction to the uniqueness of M .

Therefore we have v



= v in (5.50), and then

RHS of (5.50) = ω(B

∗

− v + u)+ω(B

◦

+ v − u)=ω(B)+ω(B



Hence follows ω(B)+6ω(B, B



) ≤ ω(B



). The reverse inequality has already

been shown in the upper-bound lemma (Lemma 5.2.29). Note that B



∈B

follows from ω(B



) = −∞.

(2) By straightforward calculations as follows:

ω(B

◦

,u,v)=ω(B − u

◦

+ v

◦

− u + v) − ω(B −u

◦

+ v

◦

)

= ω(B



) − ω(B) − ω(B,u

◦

)

= 6ω(B,B



) − ω(B, u

◦

)

= ω(B, u,v),

ω(B

◦

,u,u

◦

)=ω(B − u + v

◦

) − ω(B − u

◦

+ v

◦

)

= ω(B, u,v

◦

) − ω(B, u

◦

ω(B

◦

,v)=ω(B − u

◦

+ v) − ω(B −u

◦

+ v

◦

)

= ω(B, u

◦

,v) − ω(B, u

◦

Lemma 5.2.34. Let B ∈Band B



⊆ V with |B



| = |B|. If there exists

exactly one maximum-weight perfect matching M in G(B,B



), then for any

◦

) ∈ M the following hold true.

(1) B

◦

≡ B − u

◦

+ v

◦

∈B.

(2) There exists exactly one maximum-weight perfect matching in G(B

◦



(3) 6ω(B

◦



)=6ω(B,B



) − ω(B, u

◦

Proof. (1) This is obvious.

(2) Using the notation in Lemma 5.2.32 we have M = {(u

) | i =

1, ···,m} and (u

◦

)=(u

) for some k.Put

= B

◦

− u

+ v

= B −{u

◦

} + {v

◦

}

304 5. Polynomial Matrix and Valuated Matroid

for i = k, j = k. It then follows from (5.46) and (5.48) that

ω(B

◦

)

= ω(B

) − ω(B

◦

)

≤ 6ω(B, B

) − ω(B, u

)

= max [ω(B, u

)+ω(B,u

),ω(B, u

)+ω(B,u

)]

−ω(B,u

)

≤ [6p(u

)+6p(u

) − 6p(v

)] − [6p(u

) − 6p(v

)]

= 6p(u

) − 6p(v

where the second inequality is strict for i<j.Fori = j, on the other hand,

both inequalities are satisﬁed with equalities, since G(B,B

) has a unique

maximum-weight perfect matching {(u

), (u

◦

)} and Lemma 5.2.33 im-

plies ω(B

◦

)=ω(B,u

)=6p(u

) − 6p(v

). Thus, the potential 6p for

(B,B



) serves as a certiﬁcate of the unique-max condition also for (B

◦



(3) 6ω(B

◦





i=k

(6p(u

) − 6p(v

)) = 6ω(B,B



) − ω(B, u

◦

We are now in a position to state a main result of this section. The

“unique-max lemma” below, due to Murota [224], is a quantitative extension

of the unique-matching lemma (Lemma 2.3.18).

Lemma 5.2.35 (Unique-max lemma). Let B ∈Band B



⊆ V with



| = |B|. If there exists exactly one maximum-weight perfect matching in

G(B,B



), then B



∈Band

ω(B



)=ω(B)+6ω(B, B



). (5.51)

Proof. By induction on m = |B \ B



|. The case of m = 1 is obvious. So

assume m ≥ 2. Take any (u

◦

) contained in the unique maximum-weight

perfect matching, and put B

◦

= B−u

◦

.(B

◦



) satisﬁes the unique-max

condition by Lemma 5.2.34(2), and we have

ω(B



)=ω(B

◦

)+6ω(B

◦



)

by the induction hypothesis. By Lemma 5.2.34(3) we see

6ω(B

◦



)=6ω(B,B



) − ω(B, u

◦

)

while ω(B

◦

)=ω(B)+ω(B,u

◦

) by deﬁnition. Hence follows (5.51).

Remark 5.2.36. A remark is in order on the relation between “unique-

matching condition” (= uniqueness of a perfect matching in G(B,B



))

and “unique-max condition” (= uniqueness of the maximum-weight perfect

matching in G(B, B



)). Obviously the former implies the latter, and not con-

versely in general. However, for a separable valuation, induced from a linear

weighting (Example 5.2.2), these two conditions are equivalent, and conse-

quently the unique-max lemma reduces to the unique-matching lemma. See

also Frank [76, Lemma 2] in this connection. 2

5.2 Valuated Matroid 305

Remark 5.2.37. There is an alternative proof of the unique-max lemma,

suggested by A. Seb˝o, that makes use of the unique-matching lemma as well

as the upper-bound lemma in contrast to the above proof. Let 6p :(B \B



) ∪



\B) → R be as in Lemma 5.2.32 and extend it to p : V → R by deﬁning

p(v)=

⎧

⎨

⎩

6p(v)(v ∈ (B \ B



) ∪ (B



\ B))

+M (v ∈ B ∩B



)

−M (v ∈ V \(B



∪ B))

with a suﬃciently large M>0. We abbreviate ω[p] of (5.16) to ω

. It follows

from Theorem 5.2.26 (“only if” part) that the family of the maximizers of

= {B



∈B|ω



) ≥ ω



)(B



∈B)}

forms the basis family of a matroid, say M

=(V,B

). We claim that B ∈B

To see this, ﬁrst note that



) − ω

(B) ≤ ω(B



) − ω(B) − M/2 ≤ 0

unless B ∩ B



⊆ B



⊆ B ∪B



.IfB ∩B



⊆ B



⊆ B ∪B



, on the other hand,

we have ω



) − ω

(B) ≤ 0 by the upper-bound lemma and the inequality

(B,u, v)=ω(B, u,v) − 6p(u)+6p(v) ≤ 0(u ∈ B \ B



,v ∈ B



\ B).

We also claim that the exchangeability graph G

(B,B



)inM

has a unique

perfect matching, since B − u

+ v

∈B

(1 ≤ i ≤ m)andB − u

+ v

∈B

(1 ≤ i<j≤ m) by (5.48). By applying the unique-matching lemma to the

given pair (B,B



) in the matroid M

=(V, B

), we obtain B



∈B

,which

means ω



)=ω

(B), i.e.,

ω(B



)=ω(B)+



i=1

6p(u

) −



i=1

6p(v

)=ω(B)+6ω(B, B



The following lemma will be used in §5.2.12.

Lemma 5.2.38. Under the same assumption as in Lemma 5.2.35, let 6p, u

and v

be as in Lemma 5.2.32. Then

ω(B



) ≤ 6p(v

) − 6p(u

)(1≤ i, j ≤ m).

Proof. Putting B



= B



− v

+ u

and using Lemma 5.2.29, Lemma 5.2.35,

and (5.48) we see

ω(B



)=ω(B



) − ω(B



) ≤ 6ω(B, B



) − 6ω(B,B



)

≤

⎡

⎣



k=i

6p(u

) −



k=j

6p(v

)

⎤

⎦

−



k=1

6p(u

) −



k=1

6p(v

)

(

= 6p(v

) − 6p(u

306 5. Polynomial Matrix and Valuated Matroid

5.2.9 Valuated Independent Assignment Problem

The independent matching problem (§2.3.5) is generalized in this section

to a weighted version, called the valuated independent assignment problem,

introduced by Murota [224, 225].

The problem we consider is the following:

[Valuated independent assignment problem (VIAP)]

Given a bipartite graph G =(V

−

; A), a pair of valuated matroids

=(V

, B

,ω

)andM

−

=(V

−

, B

−

,ω

−

), and a weight function

w : A → R, ﬁnd a matching M (⊆ A) that maximizes

Ω(M ) ≡ w(M )+ω

(∂

M)+ω

−

(∂

−

M) (5.52)

subject to the constraint

∂

M ∈B

,∂

−

M ∈B

−

, (5.53)

where w(M)=



{w(a) | a ∈ M},and∂

M (resp., ∂

−

M) denotes the set of

vertices in V

(resp., V

−

) incident to M. A matching M satisfying the con-

straint (5.53) is called an independent assignment. Obviously, an independent

assignment is an independent matching in the sense of §2.3.5.

The above problem reduces to the independent assignment problem of

Iri–Tomizawa [133] if the valuations are trivial with ω

=0onB

[Independent assignment problem (IAP)]

Given a bipartite graph G =(V

−

; A), a pair of matroids M

, B

)andM

−

=(V

−

, B

−

), and a weight function w : A →

R, ﬁnd a matching M (⊆ A) that maximizes w(M) subject to the

constraint ∂

M ∈B

, ∂

−

M ∈B

−

The special case of IAP where the matroids are free with B

and B

−

coincides with the conventional assignment problem, and the

further special case with w ≡ 0 is the problem of ﬁnding a perfect matching.

Another series of specializations of VIAP is obtained by choosing a very

special underlying graph G

≡

=(V

−

; A

≡

) that represents a one-to-one

correspondence between V

and V

−

. In other words, given a pair of valu-

ated matroids M

=(V,B

,ω

)andM

=(V,B

,ω

) deﬁned on a common

ground set V , and a weight function w : V → R, we consider a VIAP in

which V

and V

−

are disjoint copies of V and A

≡

= {(v

−

) | v ∈ V },

where v

∈ V

and v

−

∈ V

−

denote the copies of v ∈ V ,andM

and

−

are isomorphic to M

and M

, respectively. The VIAP in this case is

equivalent to

[Valuated matroid intersection problem]

Given a pair of valuated matroids M

=(V,B

,ω

)andM

(V,B

,ω

) and a weight function w : V → R, ﬁnd a common base

B ∈B

∩B

that maximizes w(B)+ω

(B)+ω

(B),

5.2 Valuated Matroid 307

where w(B)=



v∈B

w(v). If the valuations are trivial with ω

=0onB

this reduces to

[Optimal common base problem]

Given a pair of matroids M

=(V,B

)andM

=(V,B

) and a

weight function w : V → R, ﬁnd a common base B ∈B

∩B

that

maximizes w(B).

A further special case with w ≡ 0 is the problem of ﬁnding a common base

of two matroids.

The following two problems also fall into the category of VIAP.

[Disjoint bases problem]

Given a pair of valuated matroids M

=(V,B

,ω

)andM

(V,B

,ω

), ﬁnd disjoint bases B

and B

(i.e., B

∩B

= ∅, B

∈B

and B

∈B

) that maximize ω

)+ω

[Partition problem]

Given a pair of valuated matroids M

=(V,B

,ω

)andM

(V,B

,ω

), ﬁnd a partition (B,V \B)ofV that maximizes ω

(B)+

(V \ B).

The disjoint bases problem for more than two valuated matroids can also

be formulated as a valuated independent assignment problem (on a bipartite

graph similar to Fig. 2.11). The partition problem is an intersection problem

in disguise, since it is the intersection problem for M

and (M

)

∗

, the dual

of M

In the ordinary independent matching problem (§2.3.5), the constraint

imposed on a matching M is that ∂

M be independent in M

rather than

that ∂

M be a base in M

. This motivates us to consider the following

extension of VIAP parametrized by an integer k:

[VIAP(k)]

Given a bipartite graph G =(V

−

; A), a pair of valuated matroids

=(V

, B

,ω

)andM

−

=(V

−

, B

−

,ω

−

), and a weight function

w : A → R, ﬁnd a matching M (⊆ A) that maximizes

Ω(M, B

−

) ≡ w(M)+ω

)+ω

−

)

subject to the constraint that |M| = k and

∂

M ⊆ B

∈B

,∂

−

M ⊆ B

−

∈B

−

. (5.54)

Obviously, VIAP(k) with k = max(r

−

) agrees with the original VIAP,

where r

=rankM

and r

−

=rankM

−

. Note that VIAP(k) with k =

max(r

−

) is feasible only if r

= r

−

and the same is true for VIAP. A

special case of VIAP(k) with trivial valuations ω

= 0 and trivial weighting

vector w =0reads:

308 5. Polynomial Matrix and Valuated Matroid

[Independent matching problem]

Given a bipartite graph G =(V

−

; A) and a pair of matroids

=(V

, I

)andM

−

=(V

−

, I

−

), ﬁnd a matching M (⊆ A)

such that |M| = k, ∂

M ∈I

,and∂

−

M ∈I

−

This problem may be regarded as a variant of the independent matching prob-

lem treated in §2.3.5. The VIAP(k) contains another well-studied important

problem:

[Weighted matroid intersection problem]

Given a pair of matroids M

=(V,I

)andM

=(V,I

) and a weight

function w : V → R, ﬁnd a common independent set I ∈I

∩I

size k that maximizes w(I).

In the above we have demonstrated that VIAP(k) contains a host of

important problems. Finally, we explain that we can formulate VIAP(k)asan

instance of the original VIAP. This fact justiﬁes our subsequent developments

focusing on the original VIAP.

For an instance of VIAP(k), we consider a VIAP on a bipartite graph

=(V

−

; A

) with valuated matroids M

=(V

, B

,ω

)andM

−

, B

−

,ω

−

) deﬁned as follows. Let r

and r

−

denote the ranks of the given

valuated matroids M

and M

−

, respectively. The graph G

=(V

−

; A

)

is deﬁned by

= V

∪ U

≡{u

| 1 ≤ i ≤ r

−

− k},

−

= V

−

∪ U

−

≡{u

−

| 1 ≤ i ≤ r

− k},

= A ∪{(u, u

−

) | u ∈ V

−

∈ U

−

}∪{(u

,u) | u ∈ V

−

∈ U

The valuated matroid M

is the direct sum of M

and the free matroid on

with trivial valuation (which is zero), i.e., B

= {B ∪U

| B ∈B

} and

(B ∪ U

)=ω

(B)forB ∈B

. Similarly for M

−

. Note that M

and

−

have a common rank equal to r

+ r

−

− k. The weight w

: A

→ R is

deﬁned by

(a)=



w(a)(a ∈ A)

0(a ∈ A

\ A).

With an independent assignment M

in G

we can associate a feasible so-

lution (M,B

−

) for VIAP(k) by deﬁning M = M

∩A, B

= ∂

and B

−

= ∂

−

\ U

−

. Conversely, from (M,B

−

) feasible for VIAP(k)

we can construct an independent assignment M

in G

.Moreover,forthe

objective function Ω(M, B

−

)ofVIAP(k), we have Ω(M, B

−

)+ω

(∂

)+ω

−

(∂

−

), in agreement with the objective function

of the associated VIAP.

5.2.10 Optimality Criteria

In this section we establish two forms of optimality criteria for the valuated in-

dependent assignment problem (VIAP). The ﬁrst criterion refers to a “poten-

5.2 Valuated Matroid 309

tial” function and the second to “negative cycles.” Both criteria are natural

extensions of the well-established corresponding results for the independent

assignment problem. Recall that the VIAP is given in terms of a bipartite

graph G =(V

−

; A), a pair of valuated matroids M

=(V

, B

,ω

)

and M

−

=(V

−

, B

−

,ω

−

), and a weight function w : A → R.

Potential Criterion. The ﬁrst optimality criterion is stated in the following

theorem of Murota [224]. The formulation in (1) refers to the existence of

a “potential” function, whereas its reformulation in (2) reveals its duality

nature.

Theorem 5.2.39 (Potential criterion for VIAP).

(1) An independent assignment M in G is optimal for the valuated inde-

pendent assignment problem (5.52)–(5.53) if and only if there exists a “po-

tential” function p : V

∪ V

−

→ R such that

(i) w(a) − p(∂

a)+p(∂

−



≤ 0(a ∈ A)

=0(a ∈ M),

(ii) ∂

M is a maximum-weight base of M

with respect to ω

(iii) ∂

−

M is a maximum-weight base of M

−

with respect to ω

−

[−p

−

where p

is the restriction of p to V

,andω

] (resp., ω

−

[−p

−

]) is the

similarity transformation deﬁned in (5.16); namely,

](B

)=ω



{p(u) | u ∈ B

} (B

⊆ V

−

[−p

−

](B

−

)=ω

−

) −



{p(u) | u ∈ B

−

} (B

−

⊆ V

−

(2) max

{Ω(M ) | M: independent assignment}

= min

{max(ω

]) + max(ω

−

[−p

−

]) |

w(a) − p(∂

a)+p(∂

−

a) ≤ 0(a ∈ A)}.

(3) If ω

, ω

−

,andw are all integer-valued, the potential p in (1) and (2)

can be taken to be integer-valued.

(4) Let p be a potential that satisﬁes (i)–(iii) in (1) for some (optimal)

independent assignment M = M

. An independent assignment M



is optimal

if and only if it satisﬁes (i)–(iii) (with M replaced by M



Proof. The proof is given later.

The optimality condition for the valuated matroid intersection problem

deserves a separate statement in a form of weight splitting, though it is

an immediate corollary of the above theorem. Recall that the intersection

problem is to maximize w(B)+ω

(B)+ω

(B) for a pair of valuated matroids

=(V,B

,ω

)andM

=(V,B

,ω

) and a weight function w : V → R.

310 5. Polynomial Matrix and Valuated Matroid

Theorem 5.2.40 (Weight splitting for valuated matroid intersec-

tion).

(1) A common base B of M

=(V, B

,ω

) and M

=(V, B

,ω

) maxi-

mizes w(B)+ω

(B)+ω

(B) if and only if there exist w

: V → R such

that

(i) [“weight splitting”] w(v)=w

(v)+w

(v)(v ∈ V ),

(ii) B is a maximum-weight base of M

with respect to ω

(iii) B is a maximum-weight base of M

with respect to ω

where ω

] (resp., ω

]) is the similarity transformation deﬁned in (5.16).

(2) max

{w(B)+ω

(B)+ω

(B)}

= min

{max(ω

]) + max(ω

]) | w(v)=w

(v)+w

(v)(v ∈ V )}.

(3) If ω

, ω

,andw are all integer-valued, we may assume that w

V → Z.

Proof. Formulate the valuated matroid intersection problem as the VIAP on

≡

=(V

−

; A

≡

) as deﬁned in §5.2.9, and apply Theorem 5.2.39 above.

By putting ω

= 0 in the above theorems we can obtain the standard re-

sults for the independent assignment problem and the optimal common base

problem, as well as for the related problems such as the weighted matroid in-

tersection problem. For these results, see Bixby–Cunningham [13], Edmonds

[68, 70], Faigle [74], Frank [76, 77], Fujishige [79, 82], Iri–Tomizawa [133],

Lawler [170, 171], Welsh [333], and Zimmermann [352].

Remark 5.2.41. The optimality criterion in Theorem 5.2.40(2) can be re-

formulated as a Fenchel-type duality between a pair of matroid valuations and

their conjugate functions, as reported in Murota [230]. It is also mentioned

that Theorem 5.2.39 can be extended for the submodular ﬂow problem with

a certain nonlinear objective function, called M-convex function (see Murota

[227, 231, 234]). 2

Negative-cycle Criterion. To describe the second criterion for optimality

in VIAP we need to introduce an auxiliary graph

A) associated

with an independent assignment M. We put B

= ∂

M and B

−

= ∂

−

The vertex set

V of

is given by

V = V

∪V

−

and the arc set

A consists

of four disjoint parts:

A = A

◦

∪ M

◦

∪ A

−

where

◦

= {a | a ∈ A} (copy of A),

◦

= {a | a ∈ M } (a: reorientation of a),

= {(u, v) | u ∈ B

,v ∈ V

\ B

− u + v ∈B

−

= {(v, u) | u ∈ B

−

,v ∈ V

−

\ B

−

− u + v ∈B

−

5.2 Valuated Matroid 311

In addition, arc length γ

(a)(a ∈

A) is deﬁned by

(a)=

⎧

⎪

⎨

⎪

⎩

−w(a)(a ∈ A

◦

)

a)(a =(u, v) ∈ M

◦

, a =(v, u) ∈ M)

−ω

,u,v)(a =(u, v) ∈ A

)

−ω

−

,u,v)(a =(v, u) ∈ A

−

)

where ω

,u,v)andω

−

,u,v) are deﬁned according to (5.21). A di-

rected cycle of negative length will be called a negative cycle.

The second criterion for optimality is stated in the following theorem of

Murota [224].

Theorem 5.2.42 (Negative-cycle criterion for VIAP). An indepen-

dent assignment M in G is optimal for the valuated independent assignment

problem (5.52)–(5.53) if and only if there exists in

no negative cycle with

respect to the arc length γ

Proof. The proof is given later.

Remark 5.2.43. The arcs of A

or A

−

represent the exchangeability in the

respective matroids. In fact, the subgraphs (V

) and (V

−

)of

can be identiﬁed respectively with the exchangeability graphs G(B

)forM

and G(B

−

)forM

−

introduced in §5.2.8. Note, however,

that the arc length in

is the negative of the arc weight in G(B

)

or G(B

−

\ B

−

). 2

Proof of the Optimality Criteria. The main body of the proof consists in

proving the equivalence of the following three conditions for an independent

assignment M:

(OPT) M is optimal,

(NNC) There is no negative cycle in

(POT) There exists a potential p with (i)–(iii) in Theorem 5.2.39(1).

We prove (OPT) ⇒ (NNC) ⇒ (POT) ⇒ (OPT). We abbreviate γ

to γ

whenever convenient.

(OPT) ⇒ (NNC): Suppose

has a negative cycle. Let Q (⊆

A)bethe

arc set of a negative cycle having the smallest number of arcs, and put

=(B

\{∂

a | a ∈ Q ∩ A

}) ∪{∂

−

a | a ∈ Q ∩ A

}, (5.55)

−

=(B

−

\{∂

−

a | a ∈ Q ∩ A

−

}) ∪{∂

a | a ∈ Q ∩ A

−

}, (5.56)

where B

= ∂

M and B

−

= ∂

−

M as before.

Lemma 5.2.44. (B

, B

) and (B

−

, B

−

) satisfy the unique-max condition

in M

and M

−

respectively.