Flow network

A flow network is a tuple G = (V, E, s, t, c).

• Digraph (V, E) with source s \in V and sink t \in V.
• Capacity c(e) \ge 0 for each e \in E.

Intuition. Material flowing through a transportation network; material originates at source and is sent to sink.

Minimum-cut problem

Def. An st-cut (cut) is a partition (A, B) of the nodes with s \in A and t \in B.

Def. Its capacity is the sum of the capacities of the edges from A to B.

• cap(A,B) = \sum_{e\ \text{out}\ A} c(e)

Min-cut problem. Find a cut of minimum capacity.

Maximum-flow problem

Def. An st-flow (flow) f is a function that satisfies:

• [capacity] For each e \in E: 0 \le f(e) \le c(e)
• [flow conservation] For each v \in V - \{s, t\}: \sum_{e\ \text{into}\ v} f(e) = \sum_{e\ \text{out}\ v} f(e)

Maximum-flow problem (cont.)

Def. The value of a flow f is: val(f) = \sum_{e\ \text{out}\ s} f(e) - \sum_{e\ \text{into}\ s} f(e)

Max-flow problem. Find a flow of maximum value.

Toward a max-flow algorithm

Greedy algorithm.

• Start with f(e) = 0 for each edge e \in E.

Toward a max-flow algorithm

Greedy algorithm.

• Start with f(e) = 0 for each edge e \in E.
• Find an s \leadsto t path P where each edge has f(e) < c(e).

Toward a max-flow algorithm

Greedy algorithm.

• Start with f(e) = 0 for each edge e \in E.
• Find an s \leadsto t path P where each edge has f(e) < c(e).
• Augment flow along path P.

Toward a max-flow algorithm

Greedy algorithm.

• Start with f(e) = 0 for each edge e \in E.
• Find an s \leadsto t path P where each edge has f(e) < c(e).
• Augment flow along path P.
• Repeat until you get stuck.

Ending flow value = 16

Toward a max-flow algorithm

Greedy algorithm.

• Start with f(e) = 0 for each edge e \in E.
• Find an s \leadsto t path P where each edge has f(e) < c(e).
• Augment flow along path P.
• Repeat until you get stuck.

But max-flow value = 19

Why greedy algorithm fails

Q. Why does the greedy algorithm fail?
A. Once greedy algorithm increases flow on an edge, it never decreases it.

Ex. Consider flow network G.

• Max flow f^\ast has f^\ast(v, w) = 0.
• Greedy algorithm could choose s \rightarrow v \rightarrow w \rightarrow t as first path.

Bottom line. Need some mechanism to “undo” a bad decision.

Residual network

Residual network (cont.)

Residual network. G_f = (V, E_f , s, t, c_f ).

• E_f = \{e: f(e) < c(e)\} \cup \{e^{-1}: f (e) > 0\}.
• Key property: f' is a flow in G_f iff f + f' is a flow in G.

Augmenting path

Def. An augmenting path is a simple s \leadsto t path in the residual network G_f.

Def. The bottleneck capacity of an augmenting path P is the minimum residual capacity of any edge in P.

Key property. Let f be a flow and let P be an augmenting path in G_f. Then, after calling f' = AUGMENT(f, c, P), the resulting f' is a flow and val(f') = val(f) + bottleneck(G_f, P).

Augmenting path: algorithm

Key property. Let f be a flow and let P be an augmenting path in G_f. Then, after calling f' = AUGMENT(f, c, P), the resulting f' is a flow and val(f') = val(f) + bottleneck(G_f, P).

AUGMENT(f, c, P)

1. \Delta = bottleneck capacity of augmenting path P.
2. FOREACH edge e \in P:
   1. IF (e \in E) f(e) = f(e) + \Delta;
   2. ELSE f(e^{-1}) = f(e^{-1}) - \Delta;
3. RETURN f;

Ford-Fulkerson algorithm

Ford-Fulkerson augmenting path algorithm.

• Start with f(e) = 0 for each edge e \in E.
• Find an s \leadsto t path P in the residual network G_f .
• Augment flow along path P.
• Repeat until you get stuck.

FORD-FULKERSON(G)

1. FOREACH edge e \in E: f(e) = 0;
2. G_f = residual network of G with respect to flow f;
3. WHILE (there exists an s \leadsto t path P in G_f)
   1. f = AUGMENT(f, c, P);
   2. Update G_f;
4. RETURN f;

Demo: Ford-Fulkerson

Flows and cuts: relationship

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the value of the flow f equals the net flow across the cut (A, B).

val(f) = \sum_{e\ \text{out}\ A} f(e) - \sum_{e\ \text{into}\ A} f(e)

Flows and cuts: relationship (cont.)

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the value of the flow f equals the net flow across the cut (A, B).

val(f) = \sum_{e\ \text{out}\ A} f(e) - \sum_{e\ \text{into}\ A} f(e)

Pf.

\begin{aligned} val(f) & = \sum_{e\ \text{out}\ s} f(e) - \sum_{e\ \text{into}\ s} f(e) \\ & = \sum_{v \in A} (\sum_{e\ \text{out}\ v} f(e) - \sum_{e\ \text{into}\ v} f(e)) \\ & = \sum_{e\ \text{out}\ A} f(e) - \sum_{e\ \text{into}\ A} f(e) \\ \end{aligned}

Flows and cuts: duality

Weak duality. Let f be any flow and (A, B) be any cut. Then, val(f) \le cap(A, B).
Pf.

\begin{aligned} val(f) & = \sum_{e\ \text{out}\ A} f(e) - \sum_{e\ \text{into}\ A} f(e) \\ & \le \sum_{e\ \text{out}\ A} f(e) \\ & \le \sum_{e\ \text{out}\ A} c(e) \\ & = cap(A, B) \\ \end{aligned}

Certificate of optimality

Corollary. Let f be a flow and let (A, B) be any cut. If val(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.
Pf.

• For any flow f': val(f') \le cap(A, B) = val(f).
• For any cut (A', B'): cap(A', B') \ge val(f) = cap(A, B).

Max-flow min-cut theorem I

Max-flow min-cut theorem. [strong duality] Value of a max flow = capacity of a min cut.

Augmenting path theorem. A flow f is a max flow iff no augmenting paths.

Pf. The following three conditions are equivalent for any flow f:

• A. There exists a cut (A, B) such that cap(A, B) = val(f).
• B. f is a max flow.
• C. There is no augmenting path with respect to f.
  • Or, if Ford-Fulkerson terminates, then f is max flow.

[ A \Rightarrow B ]

• Weak duality corollary.

Max-flow min-cut theorem II

Max-flow min-cut theorem. [strong duality] Value of a max flow = capacity of a min cut.

Augmenting path theorem. A flow f is a max flow iff no augmenting paths.

Pf. The following three conditions are equivalent for any flow f:

• A. There exists a cut (A, B) such that cap(A, B) = val(f).
• B. f is a max flow.
• C. There is no augmenting path with respect to f.

[ B \Rightarrow C ] We prove contrapositive: \lnot C \Rightarrow \lnot B.

• Suppose that there is an augmenting path with respect to f.
• Can improve flow f by sending flow along this path.
• Thus, f is not a max flow, contradiction.

Max-flow min-cut theorem III

[ C \Rightarrow A ]

• Let f be a flow with no augmenting paths.
• Let A = set of nodes reachable from s in residual network G_f.
• By definition of A: s \in A.
• By definition of flow f: t \notin A.

Computing a minimum cut

Theorem. Given any max flow f, can compute a min cut (A, B) in O(m) time.
Pf. Let A = set of nodes reachable from s in residual network G_f.

• argument from previous slide implies that capacity of (A, B) = value of flow f

Ford-Fulkerson: analysis

Assumption. Every edge capacity c(e) is an integer between 1 and C.

Integrality invariant. Throughout Ford-Fulkerson, every edge flow f(e) and residual capacity c_f(e) is an integer.
Pf. By induction on the number of augmenting paths.

Ford-Fulkerson: exponential example

Q. Is generic Ford-Fulkerson algorithm poly-time in input size (m, n, \log C)?
A. No. If max capacity is C, then algorithm can take \ge C iterations.

• See Demo.

Quiz: Ford-Fulkerson

The Ford-Fulkerson algorithm is guaranteed to terminate if the edge capacities are …

A. Rational numbers.
B. Real numbers.
C. Both A and B.
D. Neither A nor B.

Choosing good augmenting paths

Use care when selecting augmenting paths.

• Some choices lead to exponential algorithms.
• Clever choices lead to polynomial algorithms.

Pathology. When edge capacities can be irrational, no guarantee that Ford-Fulkerson terminates (or converges to a maximum flow)!

• See Demo.

Choosing good augmenting paths (cont.)

Goal. Choose augmenting paths so that:

• Can find augmenting paths efficiently.
• Few iterations.

Choose augmenting paths with:

• Max bottleneck capacity (“fattest”).
  • How to find?
  • [Next] Sufficiently large bottleneck capacity.
• [Ahead] Fewest edges.

Capacity-scaling

Overview. Choosing augmenting paths with “large” bottleneck capacity.

• Maintain scaling parameter \Delta.
• Let G_f(\Delta) be the part of the residual network containing only those edges with capacity \ge \Delta.
• Any augmenting path in G_f(\Delta) has bottleneck capacity \ge \Delta.

Capacity-scaling: algorithm

CAPACITY-SCALING(G)

1. FOREACH edge e \in E: f(e) = 0;
2. \Delta = largest power of 2 \le C;
3. WHILE (\Delta \ge 1)
   1. G_f(\Delta) = \Delta-residual network of G with respect to flow f;
   2. WHILE (there exists an s \leadsto t path P in G_f(\Delta))
      1. f = AUGMENT(f, c, P);
      2. Update G_f(\Delta);
   3. \Delta = \Delta / 2;
4. RETURN f;

Capacity-scaling: correctness

Assumption. All edge capacities are integers between 1 and C.

Invariant. The scaling parameter \Delta is a power of 2.
Pf. Initially a power of 2; each phase divides \Delta by exactly 2.

Integrality invariant. Throughout the algorithm, every edge flow f(e) and residual capacity c_f(e) is an integer.
Pf. Same as for generic Ford-Fulkerson.

Capacity-scaling: analysis

Lemma 1. There are 1 + \lfloor \log_2 C \rfloor scaling phases.
Pf. Initially C/ 2 < \Delta \le C; \Delta decreases by a factor of 2 in each iteration.

Lemma 2. Let f be the flow at the end of a \Delta-scaling phase. Then, the max-flow value \le val(f) + m \Delta.
Pf. Next slide.

Lemma 3. There are \le 2m augmentations per scaling phase.
Pf.

• Let f be the flow at the beginning of a \Delta-scaling phase.
• Lemma 2 \Rightarrow max-flow value \le val(f) + m (2 \Delta).
• Each augmentation in a \Delta-phase increases val(f) by at least \Delta.

Capacity-scaling: analysis (cont.)

Lemma 2. Let f be the flow at the end of a \Delta-scaling phase. Then, the max-flow value \le val(f) + m \Delta.
Pf.

• We show there exists a cut (A, B) such that cap(A, B) \le val(f) + m \Delta.
• Choose A to be the set of nodes reachable from s in G_f(\Delta).
• By definition of A: s \in A; By definition of flow f: t \notin A.

Capacity-scaling: running time

Lemma 1. There are 1 + \lfloor \log_2 C \rfloor scaling phases.

Lemma 2. Let f be the flow at the end of a \Delta-scaling phase. Then, the max-flow value \le val(f) + m \Delta.

Lemma 3. There are \le 2m augmentations per scaling phase.

Theorem. The capacity-scaling algorithm takes O(m^2 \log C) time.
Pf.

• Lemma 1 + Lemma 3 \Rightarrow O(m log C) augmentations.
• Finding an augmenting path takes O(m) time.

Shortest augmenting

Q. How to choose next augmenting path in Ford-Fulkerson?
A. Pick one that uses the fewest edges (via BFS).

SHORTEST-AUGMENTING-PATH(G)

1. FOREACH e \in E: f(e) = 0;
2. G_f = residual network of G with respect to flow f;
3. WHILE (there exists an s \leadsto t path in G_f)
   1. P = BREADTH-FIRST-SEARCH(G_f);
   2. f = AUGMENT(f, c, P);
   3. Update G_f;
4. RETURN f;

Shortest augmenting: analysis overview

Lemma 1. The length (number of edges) of a shortest augmenting path never decreases.
Pf. Ahead.

Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.
Pf. Ahead.

Level graph

Def. Given a digraph G = (V, E) with source s, its level graph is defined by:

• l(v) = number of edges in shortest s \leadsto v path.
• L_G = (V, E_G) is the subgraph of G that contains only those edges (v, w) \in E with l(w) = l(v) + 1.

Level graph (cont.)

Key property. P is a shortest s \leadsto v path in G iff P is an s \leadsto v path in L_G.

• nodes are ordered the same with BFS
• “back-edges” are removed

Shortest augmenting: Lemma 1

Lemma 1. The length of a shortest augmenting path never decreases.

• Let f and f' be flow before and after a shortest-path augmentation.
• Let L_G and L_Gʹ be level graphs of G_f and G_f'.
• Only back edges added to G_f'; bottleneck broken.
• any s \leadsto t path uses back edge is longer than previous length.

Shortest augmenting: Lemma 2

Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.

• At least one (bottleneck) edge is deleted from L_G per augmentation.
• No new edge added to L_G until shortest path length strictly increases.

Shortest augmenting: analysis

Lemma 1. The length (number of edges) of a shortest augmenting path never decreases.

Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.

Theorem. The shortest-augmenting-path algorithm takes O(m^2 n) time.

Dinitz’ algorithm

Two types of augmentations.

• Normal: length of shortest path does not change.
• Special: length of shortest path strictly increases.

Phase of normal augmentations.

• Construct level graph L_G.
• Start at s, advance along an edge in L_G until reach t or get stuck.
  • If reach t, augment flow; update L_G; and restart from s.
  • If get stuck, delete node from L_G and retreat to previous node.

Demo: Dinitz’ algorithm

Dinitz’ algorithm (refined)

Quiz: level graph

How to compute the level graph L_G efficiently?

A. Depth-first search.
B. Breadth-first search.
C. Both A and B.
D. Neither A nor B.

Dinitz’ algorithm: analysis

Lemma. A phase can be implemented to run in O(m n) time.
Pf.

• Initialization happens once per phase. O(m) using BFS.
• At most m augmentations per phase. O(mn) per phase.
  • (because an augmentation deletes at least one edge from L_G)
• At most n retreats per phase. O(m + n) per phase
  • (because a retreat deletes one node from L_G)
• At most mn advances per phase. O(mn) per phase
  • (because at most n advances before retreat or augmentation)

Maximum-flow algorithms: practice

Push-relabel algorithm. [Goldberg-Tarjan 1988] Increases flow one edge at a time instead of one augmenting path at a time.

• (SECTION 7.4, Algorithm Design.)

Maximum-flow algorithms: CV

Computer vision. Different algorithms work better for some dense problems that arise in applications to computer vision.

• [Boykov and Kolmogorov 2004] An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision.

Quiz: bipartite matching

Which max-flow algorithm to use for bipartite matching?

A. Ford-Fulkerson: O(m n C).
B. Capacity scaling: O(m^2 log C).
C. Shortest augmenting path: O(m^2 n).
D. Dinitz’ algorithm: O(m n^2).

Simple unit-capacity networks

Def. A flow network is a simple unit-capacity network if:

• Every edge has capacity 1.
• Every node (other than s or t) has exactly one entering edge, or exactly one leaving edge, or both.

Ex. Bipartite matching.

Unit-capacity: algorithm overview

Shortest-augmenting-path algorithm.

• Normal augmentation: length of shortest path does not change.
• Special augmentation: length of shortest path strictly increases.

Unit-capacity: Dinitz’

Phase of normal augmentations.

• Construct level graph L_G.
• Start at s, advance along an edge in L_G until reach t or get stuck.
• If reach t, augment flow; update L_G; and restart from s.
• If get stuck, delete node from L_G and go to previous node.

Demo: Dinitz’ for Unit-capacity

Unit-capacity: Lemma 1

Phase of normal augmentations.

• Construct level graph L_G.
• Start at s, advance along an edge in L_G until reach t or get stuck.
• If reach t, augment flow; update L_G; and restart from s.
• If get stuck, delete node from L_G and go to previous node.

Lemma 1. A phase of normal augmentations takes O(m) time.
Pf.

• O(m) to create level graph L_G.
• O(1) per edge (each edge involved in at most one advance, retreat, and augmentation).
• O(1) per node (each node deleted at most once).

Quiz: non-unit-capacity

Consider running advance-retreat algorithm in a unit-capacity network (but not necessarily a simple one). What is running time?

A. O(m).
B. O(m^{3/2}).
C. O(m n).
D. May not terminate.

Hint: both indegree and outdegree of a node can be larger than 1.

Unit-capacity: Lemma 2

Lemma 2. After n^{1/2} phases, val(f) \ge val(f^\ast) - n^{1/2}.

• After n^{1/2} phases, length of shortest augmenting path is > n^{1/2}.
• Thus, level graph has \ge n^{1/2} levels (not including levels for s or t).
• Let 1 \le h \le n^{1/2} be a level with min number of nodes \Rightarrow |V_h| \le n^{1/2}.

Unit-capacity: Lemma 2 (cont.)

Lemma 2. After n^{1/2} phases, val(f) \ge val(f^\ast) - n^{1/2}.

• After n^{1/2} phases, length of shortest augmenting path is > n^{1/2}.
• Thus, level graph has \ge n^{1/2} levels (not including levels for s or t).
• Let 1 \le h \le n^{1/2} be a level with min number of nodes \Rightarrow |V_h| \le n^{1/2}.
• Let A = \{v : l(v) < h\} \cup \{v : l(v) = h\ \text{and}\ v\ \text{has}\ \le 1\ \text{outgoing residual edge}\}.
• cap_f (A, B) \le |V_h| \le n^{1/2} \Rightarrow val(f) \ge val(f^\ast) - n^{1/2}.

Unit-capacity: analysis

Theorem. [Even-Tarjan 1975] In simple unit-capacity networks, Dinitz’ algorithm computes a maximum flow in O(m n^{1/2}) time.
Pf.

• Lemma 1. Each phase of normal augmentations takes O(m) time.
• Lemma 2. After n^{1/2} phases, val(f) \ge val(f^\ast) - n^{1/2}.
• Lemma 3. After \le n^{1/2} additional augmentations, flow is optimal.