Man muss immer generalisieren. [One must always generalize.]— attributed to Carl Gustav Jacob Jacobi (c. 1830) by
Philip J. Davis and Reuben Hersh, The Mathematical Experience (1981)
Life is like riding a bicycle. To keep your balance you must keep moving.
— Albert Einstein, in a letter to his son Eduard (February 5, 1930)
Scarcely pausing for breath, Vroomfondel shouted, “We don’t demand solid facts! What we
demand is a total absence of solid facts. I demand that I may or may not be Vroomfondel!”— Douglas Adams, The Hitchhiker’s Guide to the Galaxy (1979)

F
Balances and Pseudoﬂows[Read Chapters 10 and 11 ﬁrst.]
Status: Beta. Needs more ﬁgures.

F.1

Unbalanced Flows

In this chapter, we consider a generalization of flows that allows “stuff” to be injected
or extracted from the flow network at the vertices. For the moment, consider a flow
network G = (V, E) without any specific source and target vertices. Let b : V → R be abalance function describing how much flow should be injected (if the value is positive)
or extracted (if the value is negative) at each vertex. We interpret positive balances as
demand or deficit and negative balances as (negated) supply or excess.
We now redefine the word flow to mean a function f : E → R that satisfies themodified balance conditionXX
f (u v) −f (v w) = b(v)
u∈V

w∈V

at every node v. A flow f is feasible if it satisfies the usual capacity constraints
0 ≤ f (e) ≤ c(e) at every edge e. Our problem now is to compute, given a flow network© 2018 Jeff Erickson

http://algorithms.wtf

1

F. BALANCES AND PSEUDOFLOWS

with edge capacities and vertex balances, either a feasible flow in or a proof that no suchflow exists.
Note two significant differences from the standard maximum flow problem. First,
there are no special source and target vertices that are exempt from the balance constraint.
Second, we are not trying to optimize the value of the flow; in fact, the “value” of a flow
is no longer even defined, because the network has no source and target vertices.
One easy necessary condition is that all the vertex balances must sum to zero;
intuitively, every edge u v adds the same amount to v’s balance that it subtracts fromu’s balance. More formally, for every feasible flow f , we have


X
X X
X
b(v) =f (u v) −f (v w)
v

v

=

w∈V
X u∈V
X
f (u v) −f (v w) = 0.

u v∈EF.2

v w∈E

Reduction to Maximum Flow

We can reduce the problem of finding a feasible flow in a network with non-zero balance
constraints to the standard maximum-flow problem, by adding new vertices and edges
to the input graph as follows.
Starting with with original graph G, we construct a new graph G 0 = (V 0 , E 0 ) byadding a new source vertex s with edges to every supply vertex, a new target vertex twith edges from every demand vertex. Specifically, for each vertex v in G, if b(v) > 0,
we add an edge v  t with capacity b(v), and if b(v) < 0, we add a new edge s v withcapacity −b(v). Let c 0 : E 0 → R be the resulting capacity function; by construction,c 0 | E = c.
1
+2

5

–1

20

15
15

10

–5

10

10

20
+6

s

5

10

15
10

20
+2

2
5

15

10

–4

6

10

t

20
10

4

2

A ﬂow network G with non-zero balance constraints, and the transformed network G 0 .

Now call an (s, t)-flow in G 0 saturating if every edge leaving s (or equivalently, everyedge entering t) is saturated. Every saturating flow is a maximum flow; conversely,
either all maximum flows in G 0 are saturating, or G 0 has no saturating flow.
Lemma F.1. G has a feasible flow if and only if G 0 has a saturating (s, t)-flow.
2F.2. Reduction to Maximum Flow

Proof: Let f : E → R be any feasible flow in G, and consider the function f 0 : E 0 → R
defined as follows:¨
f (e0 ) if e0 ∈ E
0 0f (e ) = 0 0c (e ) otherwise
Every edge incident to s or t is saturated, and every edge in E satisfies the capacity
constraint 0 ≤ f 0 (e) = f (e) ≤ c(e) = c 0 (e). For each vertex v except s and t, we
immediately have


X
X
X
X
f 0 (u v) −f 0 (v w) =f (u v) −f (v w) − b(v)
u∈V 0

w∈V 0

u∈V

w∈V

= b(v) − b(v)= 0.
0We conclude that f is a feasible (s, t)-flow in G 0 . Every edge out of s or into t is saturated
by definition, so f 0 is a saturating flow in G 0 .
Similarly tedious algebra implies that for any saturating (s, t)-flow f 0 : E 0 → R
through G 0 , the restriction f = f 0 | E is a feasible flow in G.

1/1
+2

5/5

–1

10/20
–5

7/15

3/10

9/15

10/10

5/10

+6

1/20
+2

5/10

2/2
5/5

10/20

s

5/5

3/10

7/15
9/15

10/10

5/10

–4

6/6

t

1/20
5/10

4/4

2/2
0

A feasible ﬂow in G and the corresponding saturating ﬂow in G .

We emphasize that there are flow networks with no feasible flow, even when thesum of the balances is zero. Suppose we partition the vertices of G into two arbitrary
subsets S and T . As usual, let kS, T k be the total capacity of the cut (S, T ):XX
kS, T k =c(u v).
u∈S v∈T

Let b(S) and b(T ) denote the sum of the balances of vertices in S and T , respectively:
X
X
b(S) :=b(u)andb(T ) :=
b(v).
u∈S

v∈T

We call the cut (S, T ) infeasible if kS, T k < b(T ); that is, if T has more demand thancan be moved across the cut. The following theorem is a straightforward consequence ofthe maxflow/mincut theorem (hint, hint):
Theorem F.2. Every flow network has either a feasible flow or an infeasible cut.
3

F. BALANCES AND PSEUDOFLOWS

F.3

Pseudoﬂows

Instead of reducing our new unbalanced flow problem to the classical maximum flow
problem, it is instructive to project the behavior of Ford-Fulkerson on the transformed
flow network G 0 back to the original flow network G. The resulting algorithm no longer
maintains and incrementally improves a feasible flow in G, but a more general function
called a pseudoflow. Formally, a pseudoflow in G is any function ψ: E → R. We saythat a pseudoflow ψ is feasible if 0 ≤ ψ(e) ≤ c(e) for every edge e ∈ E. A flow is any
pseudoflow that also satisfies the balance constraints at every vertex.
For any pseudoflow ψ in G, we define the residual capacity of any edge u v as usual:¨c(u v) − ψ(u v) if u v ∈ Ecψ (u v) :=ψ(v u)if v u ∈ E
We also define the residual balance of any node to be its original balance minus its net
incoming pseudoflow:XXbψ (v) := b(v) −ψ(u v) +ψ(v w).
u

w

A pseudoflow ψ is a flow if and only if bψ (v) = 0 for every vertex v. Finally, we define
the residual network Gψ to be the graph of all edges with positive residual capacity,where the balance of each node v is bψ (v). As usual, if ψ is zero everywhere, then Gψ isthe original network G, with its original capacities and balances.
Now we redefine an augmenting path to be any path in the residual graph Gψ fromany vertex with negative residual balance (supply or excess) to any vertex with positive
residual balance (demand or deficit). Pushing flow along an augmenting path decreases
the total residual supplyXBψ :=bψ (v)v

and therefore moves ψ closer to being a feasible flow. The largest amount of flow that
we can push along an augmenting path from u to v, before it ceases to be an augmenting
path, is the minimum of three quantities:• The residual supply −bψ (u) at the beginning of the path,• The residual demand bψ (v) at the end of the path, and• The minimum residual capacity among the edges in the path.
On the other hand, if Gψ contains a vertex v with non-zero residual balance, butdoes not contain an augmenting path starting or ending at v, then G has no feasible flow.
Specifically, if bψ (v) > 0, then the set S of vertices reachable from v and its complement
T = V \ S define an infeasible cut; symmetrically, if bψ (v) < 0, then the set T of vertices
that can reach v and its complement S = V \ T define an infeasible cut.
Putting all these pieces together, we obtain a simple algorithm for computing eithera feasible flow or an infeasible cut. Initialize ψ(e) = 0 at every edge e. Then as long4

F.3. Pseudoﬂows

+2

0/5

5/20
–5

5

–1
7/15

3/10

4/15

15

8
11

5
10/10

+6

–5

7

1/20
+2

0/10

10

5

–4

–1
7/15

–5

7/10

0/15

6/10

+6

19

4
10

0/5

9/20

7

3

5
5/10

+2

1
+5

5/10

1/20
+2

0/10

–4

From left to right: A pseudoﬂow ψ in a ﬂow network G ; the residual graph Gψ with one augmenting pathhighlighted; and the updated pseudoﬂow after pushing 4 units along the augmenting path.

as the residual graph Gψ has a vertex with non-zero balance, update ψ by pushing as
much flow as possible along an arbitrary augmenting path. When all residual balances
are zero, the current pseudoflow ψ is actual a feasible flow.
FeasibleFlow(V, E, c, b):
for every edge e ∈ E
ψ(e) ← 0P
B ← v |b(v)|/2
while B > 0
construct Gψ
〈〈Find augmenting path π〉〉s ← any vertex with bψ (s) < 0
if s cannot reach a vertex t in Gψ with bψ (t) > 0
return Infeasiblet ← any vertex reachable from s with bψ (t) > 0
π ← any path in Gψ from s to t〈〈Push as much ﬂow as possible along π〉〉
R ← min −bψ (s), bψ (t), mine∈π cψ (e)B ← B−Rfor every directed edge e ∈ πif e ∈ E
ψ(e) ← ψ(e) + R
else 〈〈rev(e) ∈ E〉〉
ψ(e) ← ψ(e) − R
return ψ

Naturally this algorithm comes with both the same power and the same limitations as
Ford-Fulkerson. We can find a single augmenting path in O(V + E) time via whatever-firstsearch. If all capacities andP balances are integers, the basic algorithm halts after at most B
iterations, where B = v |b(v)|/2, but if we allow irrational capacities 〈〈or irrationalbalances?〉〉, the algorithm could run forever without converging to a flow. Choosing theaugmenting path with maximum residual capacity or with the fewest edges leads to

ÃÃÃÃÃ

5

F. BALANCES AND PSEUDOFLOWS

faster algorithms; in particular, if we always choose the shortest augmenting path, thealgorithm runs in O(V E 2 ) time.

F.4

Variations on a Theme

There are several variations on the standard maximum-flow problem, with additionalor modified constraints, that can be solved quickly using the pseudoflow formulation.
These variations are all solved using a two-stage process:• First find a feasible flow f in the original input graph G.
• Then find a maximum flow f 0 in the residual graph G f .
• Finally, return the flow f + f 0 .
In each variation, the residual graph G f we use in the second stage will be a textbookstandard flow network. Notice that Ford-Fulkerson itself can be seen as an example ofthis two-stage algorithm, where the flow f found in the first stage is zero everywhere, ormore subtly, where f is obtained by interrupting Ford-Fulkerson after any augmentation
step.

Maximum Flows with Non-Zero Balances
Suppose we are given a flow network G = (V, E) with edge capacities c : E → R+ ,non-trivial vertex balances b : V → R, and two special vertices s and t, and we are asked
to compute the maximum (s, t)-flow in this network. In this context, an (s, t)-flow is afunction f : E → R+ that satisfies the modified balance conditionsXX
f (v w) −f (u v) = b(v)wu

at every vertex v except s and t . As usual, our goal is to find an (s, t)-flow that maximizes
the net flow out of s:
XX|f | =f (sw) −f (us)w

u

The algorithms in the previous sections almost solve the first stage directly, except
for two issues: (1) the terminal vertices s and t are not subject to balance constraints,and (2) the sum of the vertex balances need not be zero. In fact, we can handle
both of these issues at once by modifying the graph as follows. First, to avoid any
ambiguity,
Pwe (re)define b(s) = b(t) = 0. Then we add one new vertex z with balanceb(z) = − v b(v), and two new infinite-capacity edges t z and z s. Call the resulting
modified flow network G 0 . Straightforward definition-chasing implies that any feasible
flow in G 0 restricts to a feasible (s, t)-flow in G, and conversely, any feasible (s, t)-flowin G can be extended to a feasible flow in G 0 .

ÆÆÆFigure!
6F.4. Variations on a ThemeThus, we can find a feasible (s, t)-flow f in G in O(V E 2 ) time by repeatedly pushingflow along shortest augmenting paths, or in O(V E) time using Orlin’s maximum-flow
algorithm. In the resulting residual graph G f , every vertex (except at s and t) has residual
balance zero, so we can find a maximum flow in G f using any standard algorithm.

Lower Bounds on Edges
In another standard variant, the input includes a lower bound `(e) on the flow valueof each edge e, in addition to the capacity c(e). In this context, a flow f is feasible if
and only if `(e) ≤ f (e) ≤ c(e) for every edge e. In the standard flow problem, we have`(e) = 0 for every edge e.
Although it is natural to require the lower bounds `(e) to be non-negative, we can infact allow negative lower bounds, and therefore negative flow values f (e), if we interpret
negative flow along an edge u v as positive flow along its reversal v u. More formally,
we define a pseudoflow as a function ψ: E → R such thatψ(v u) = −ψ(u v)
for every edge u v; more simply, a pseudoflow is an antisymmetric function over theedges. The antisymmetry is reflected in the upper and lower bounds on flow:`(v u) = −c(u v)c(v u) = −`(u v)

Then for any pseudoflow ψ, each edge u v has both a residual capacity and a residual
lower bound, defined as follows to maintain antisymmetry:¨`(u v) − ψ(u v) if u v ∈ E`ψ (u v) :=ψ(u v) − c(v u) if v u ∈ E¨c(u v) − ψ(u v) if u v ∈ Ecψ (u v) :=ψ(u v) − `(v u) if v u ∈ E
Now the residual network Gψ consists of all edges u v with non-negative residual capacitycψ (u v) ≥ 0. We can easily verify (hint, hint) that this antisymmetric formulation of(pseudo)flows and residual graphs is completely consistent with our usual formulationof flows as non-negative functions.
Given a flow network with both lower bounds and capacities on the edges, we cancompute a maximum (s, t)-flow as follows. If all lower bounds are zero or negative,
we can apply any standard maxflow algorithm, after replacing each edge u v with anegative lower bound with a pair of opposing edges u v and v u, each with positive
capacity.1 Otherwise, we first define an initial feasible pseudoflow ψ that meets every
positive lower bound:ψ(u v) = max `(u v), 0
1
Wait, didn’t we forbid opposing edges two chapters ago? Okay, fine: Replace each edge u v with apair of opposing paths u x  v and v  y u, where x and y are new vertices.

7

F. BALANCES AND PSEUDOFLOWS

Vertices in the resulting residual graph Gψ may have non-zero residual balance, butevery edge has a lower bound that is either zero or negative. Thus, we can compute a
maximum (s, t)-flow in Gψ using the previous two-stage approach, in O(V E) time.

ÆÆÆFigure!

ªF.5

ÆÆÆPush-Relabel
This section needs ﬁgures and an editing sweep. Cite Alexander Karzanov (preﬂows)?

The pseudoflow formulation is the foundation of another family of efficient maximumflow algorithms that is not based on path-augmentation, called push-relabel or preflowpush algorithms, discovered by Andrew Goldberg and then refined in collaboration with
Robert Tarjan before formal publication in 1986, while Goldberg was still a PhD student.
Every push-relabel algorithm maintains a special type of pseudoflow, called a preflow,in which every node (except s) has non-negative residual balance:XX
ψ(u v) −ψ(v w) ≥ 0.
bψ (v) :=uw

We call a vertex active if it is not the target vertex t and its residual balance is positive;
we immediately observe that ψ is actually a flow if and only if no vertex is active. The
algorithm also maintains a non-negative integer height ht (v ) for each vertex v. We callany edge u v with ht(u) > ht(v) a downward edge.
The push-relabel algorithm begins by setting ht(s) = |V | and ht(v) = 0 for every
node v 6= s, and choosing an initial pseudoflow ψ that saturates all edges leaving s andleaves all other edges empty:¨c(u v) if u = sψ(u v) =0otherwise
Then for as long as there are active nodes, the algorithm repeatedly performs one of thefollowing operations at an arbitrary active node u:• Push: For some downward residual edge u v out of u, increase ψ(u v) by theminimum of the excess at u and the residual capacity of u v.

• Relabel: If u has no downward outgoing residual edges, increase the height of u
by 1.

It is not at all obvious (at least, it wasn’t obvious to me at first) that the push-relabel
algorithm correctly computes a maximum flow, or even that it halts in finite time. To
prove that the algorithm is correct, we need a series of relatively simple observations.
First, we say that the height function ht : V → N and the pseudoflow ψ: E → R arecompatible if ht(u) ≤ ht(v) + 1 for every edge u v in the residual graph Gψ .
8

ªF.5. Push-Relabel

Lemma F.3. After each step of the push-relabel algorithm, the height function ht andthe pseudoflow ψ are compatible.
Proof: We prove the lemma by induction. Initially, every residual edge either enters
the source vertex s or has both endpoints with height zero, so the initial heights andpseudoflow are compatible. For each later step of the algorithm, there are two cases toconsider.
• Just before we push flow along the residual edge u v, then u v must be a downwardedge, so ht(v) < ht(u). If the edge u v was empty before the push, then this step
adds the reversed edge v u to the residual graph, and ht(v) < ht(u) ≤ ht(u) + 1.

• On the other hand, just before we relabel an active vertex v, we must have ht(v) ≤ht(w) for every outgoing residual edge v w and (by the induction hypothesis)ht(u) ≤ ht(v) + 1 for every incoming residual edge u v. Thus, after relabeling, wehave ht(v) ≤ ht(w) + 1 for every outgoing residual edge v w and ht(u) ≤ ht(v) ≤ht(v) + 1 for every incoming residual edge u v.

In both cases, compatibility of the new height function and the new pseudoflow follows
from the inductive hypothesis.
Lemma F.4. After each step of the push-relabel algorithm, there is no residual pathfrom s to t.
Proof: Suppose to the contrary that there is a simple residual path v0  v1  · · ·  vk ,where v0 = s and vk = t. This path does not repeat vertices, so k < |V |. Because
the height of s and t never change, we have ht(v0 ) = |V | and ht(vk ) = 0. Finally,
compatibility implies ht(vi ) ≥ ht(vi−1 ) − 1, and thus by induction ht(vi ) ≥ ht(v0 ) − i, foreach index i. In particular, we have ht(vk ) ≥ |V | − k > 0, giving us a contradiction. 
Lemma F.5. If the push-relabel algorithm terminates, it returns a maximum (s, t)-flow.
Proof: The algorithm terminates only when there are no active vertices, which meansthat every vertex except s and t has zero residual balance. A pseudoflow with non-zero
residual balance is definition of a flow! Any flow whose residual graph has no paths
from s to t is a maximum (s, t)-flow.
For a full proof of correctness, we still need to prove that the algorithm terminates, but
the easiest way to prove termination is by proving an upper bound on the running time.
In the analysis, we distinguish between two types of push operations. A push along edgeu v is saturating if we have ψ(u v) = c(u v) after the push, and non-saturatingotherwise.
Lemma F.6. The push-relabel algorithm performs at most O(V 2 ) relabel operations.
9F. BALANCES AND PSEUDOFLOWS

Proof: At every stage of the algorithm, each active node v has a residual path back to s
(because we can follow some unit of flow from s to v). Compatibility now implies thatthe height of each active node is less than 2|V |. But we only change the height of a node
when it is active, and then only upward, so the height of every node is less than 2|V |. We
conclude that each node is relabeled at most 2|V | times.

Lemma F.7. The push-relabel algorithm performs at most O(V E) saturating pushes.
Proof: Consider an arbitrary edge u v. We only push along u v when ht(u) > ht(v).
If this push is saturating, it removes u v from the residual graph. This edge reappears
in the residual graph only when we push along the reversed edge v u, which is only
possible when ht(u) < ht(v). Thus, between any saturating push through u v and thereappearance of u v in the residual graph, vertex v must be relabeled at least twice.
Similarly, vertex u must be relabeled at least twice before the next push along u v. By
the previous lemma, u and v are each relabeled at most 2|V | times. We conclude that
there are at most |V | saturating pushes along u v.
Lemma F.8. The push-relabel algorithm performs at most O(V 2 E) non-saturatingpushes.
Proof: Define the potential Φ of the current residual graph to be the sum of the heights
of all active vertices. This potential is always non-negative, because heights are nonnegative. Moreover, we have Φ = 0 when the algorithm starts (because every active node
has height zero) and Φ = 0 again when the algorithm terminates (because there are no
active vertices).
Every relabel operation increases Φ by 1. Every saturating push along u v makes v
active (if it wasn’t already), and therefore increases Φ by at most ht(v) ≤ 2|V |. Thus,
the total potential increase from all relabels and saturating pushes is at most O(V 2 E).
On the other hand, every non-saturating push along u v makes the vertex u inactive
and makes v active (if it wasn’t already) and therefore decreases the potential by at leastht(u) − ht(v) ≥ 1.
Because the potential starts and ends at zero, the total potential decrease from all
non-saturating pushes must equal the total potential increase from the other operations.
The lemma follows immediately.
With appropriate elementary data structures, we can perform each push in O(1)time, and each relabel in time proportional to the degree of the node. It follows that thealgorithm runs in O(V 2 E) time; in particular, the algorithm always terminates with thecorrect output!
Like the Ford-Fulkerson algorithm, the push-relabel approach can be made more
efficient by carefully choosing which push or relabel operation to perform at each step.
Two natural choices lead to faster algorithms:
10

Exercises• FIFO: The active vertices are kept in a standard queue. At each step, we remove theactive vertex from the front of the queue, and then either push from or relabel thatvertex until it becomes inactive. Any newly active vertices are inserted at the back of
the queue. This rule reduces the number of non-saturating pushes to O(V 3 ), and so
the resulting algorithm runs in O(V 3 ) time.
• Highest label: At each step, we either push from or relabel the vertex with maximum
height (breaking
of non-saturating
p ties arbitrarily). This rule reduces the number ppushes to O(V 2 E), and so the resulting algorithm runs in O(V 2 E) time.
With more advanced data structures that support pushing flow along more than oneedge at a time, the running time of the push-relabel algorithm can be improved toO(V E log(V 2 /E)). (This was one of the theoretically-fastest algorithms known before
Orlin’s algorithm.) In practice, however, this optimization is usually slower than the
more basic algorithm that handles one edge at a time.

Exercises
1. Recall from Chapter 11 that a path cover of a directed acyclic graph is a collection of
directed paths, such that every vertex in G appears in at least one path. We previously
saw how to compute disjoint path covers (where each vertex lies on exactly one path)by reduction to maximum bipartite matching. Your task in this problem is to compute
path covers without the disjointness constraint.
(a) Suppose you are given a dag G with a unique source s and a unique sink t.
Describe an algorithm to find the smallest path cover of G in which every pathstarts at s and ends at t.
(b) Describe an algorithm to find the smallest path cover of an arbitrary dag G, withno additional restrictions on the paths.
2. (a) Prove that any flow f in a network G = (V, E) with non-zero balance constraints(and no source or target) can be expressed as a weighted sum of directed paths
and directed cycles, such that• each path leads from an excess node to a deficit node;• a directed edge u v appears in at least one path or cycle if and only if
f (u v) > 0; and• the total number of paths and cycles is at most E.
(b) Describe an algorithm to construct such a decomposition in O(V E) time.
3. Let G = (V, E) be an arbitrary flow network with source s and sink t. Recall that a
preflow is a pseudoflow ψ: E → R where every vertex except s has non-negative
residual balance; that is, for each vertex v, we haveXX
ψ(u v) >ψ(v w).
uw

11

F. BALANCES AND PSEUDOFLOWSA preflow ψ is feasible if 0 ≤ ψ(u v) ≤ c(u v) for every edge u v. A maximum
preflow if is a feasible preflow such that the net flow into tXX
ψ(u t) −ψ(t w)u

w

is as large as possible. Describe an algorithm to transform an arbitrary maximum
pseudoflow into a maximum flow in O(V E) time. [Hint: Flow decomposition!]
4. (a) An edge cover of an undirected graph G = (V, E) is a subset of edges C ⊆ E suchthat every vertex is the endpoint of at least one edge in C. (Thus, edge covers
are the “opposite” of matchings.) Describe and analyze an efficient algorithm tocompute the smallest edge cover of a given bipartite graph.
(b) Describe and analyze an algorithm for the following more general problem. The
input consists of a bipartite graph G = (V, E) and two functions `, u: V → N.
Your algorithm should either output a subset of edges C ⊆ E such that each vertexv ∈ V is incident to at least `(v) edges and at most u(v) edges in C, or correctly
report that no such subset exists.
5. (a) Suppose we are given a directed graph G, two vertices s and t, and two functions`, c : V → R over the vertices. An (s, t)-flow f : E → R in this network is feasible
if and only if the total flow into each vertex v (except s and t) lies between `(v)
and c(v):X`(v) ≤f (u v) ≤ c(v).
u vDescribe an efficient algorithm to compute a maximum (s, t)-flow in this network.
(b) Suppose we are given a directed graph G, two vertices s and t, and two functions
b− , b+ : V → R over the vertices. An (s, t)-flow f : E → R in this network is
feasible if and only if the total net flow into each vertex v (except s and t) lies
between b− (v) and b+ (v):XXb− (v) ≤f (u v) −f (v w) ≤ b+ (v).
u v

v w

Describe an efficient algorithm to compute a maximum (s, t)-flow in this network.
(c) Describe an efficient algorithm to compute a maximum (s, t)-flow in a networkwith all of the features we’ve seen so far:• upper and lower bounds on the flow through each edge,• upper and lower bounds on the flow into each vertex, and• upper and lower bounds on the flow balance at each vertex.

12© 2018 Jeff Erickson

http://algorithms.wtf