Exercises — Network Flows

Chapter 11 · Fully solved exercises on max-flow, min-cut, and Ford-Fulkerson

Exercise 1: Ford-Fulkerson Trace

Problem. Find the maximum flow in the network below using Ford-Fulkerson with BFS augmenting paths (Edmonds-Karp):

  • Nodes: \(s, a, b, t\)
  • Arcs and capacities: \(s \to a: 3\), \(s \to b: 4\), \(a \to b: 2\), \(a \to t: 2\), \(b \to t: 3\)

Solution. All flows are initially \(0\). We trace each BFS augmentation.

Augmentation 1. BFS from \(s\) finds the shortest path \(s \to a \to t\). Bottleneck \(= \min(3, 2) = 2\). Send 2 units. Cumulative flow value \(= 2\).

\[ f(s \to a) = 2, \quad f(a \to t) = 2. \]

Augmentation 2. Arc \(a \to t\) is now saturated. BFS finds \(s \to a \to b \to t\). Residual capacities: \(s \to a: 3-2=1\), \(a \to b: 2\), \(b \to t: 3\). Bottleneck \(= \min(1, 2, 3) = 1\). Send 1 unit. Cumulative flow value \(= 3\).

\[ f(s \to a) = 3 \ (\text{sat.}), \quad f(a \to b) = 1, \quad f(b \to t) = 1. \]

Augmentation 3. Arc \(s \to a\) is saturated. BFS finds \(s \to b \to t\). Residual capacities: \(s \to b: 4\), \(b \to t: 3-1=2\). Bottleneck \(= \min(4, 2) = 2\). Send 2 units. Cumulative flow value \(= 5\).

\[ f(s \to b) = 2, \quad f(b \to t) = 3 \ (\text{sat.}). \]

Termination. In the residual graph, the only outgoing arcs from \(s\) are \(s \to a\) (residual 0, saturated) and \(s \to b\) (residual 2). From \(b\): \(b \to t\) is saturated; the only residual arc is \(b \to a\) (backward, residual 1 from \(f(a \to b)=1\)). From \(a\): \(a \to t\) is saturated; \(a \to b\) (residual 1) leads back toward \(b\). No path from \(s\) reaches \(t\). No augmenting path exists. Algorithm terminates.

Maximum flow \(= 5\).

Min-cut verification. \(S = \{s, a, b\}\), \(T = \{t\}\). Forward arcs crossing the cut: \(a \to t \ (2)\) and \(b \to t \ (3)\). Cut capacity $= 2 + 3 = 5 = $ max flow. \(\checkmark\)

Exercise 2: Identify the Min Cut

Problem. For the network in Exercise 1 with max flow \(= 5\), find all minimum cuts, i.e., all \((S, T)\) partitions with \(s \in S\), \(t \in T\), and cut capacity \(= 5\).

Solution. Enumerate every subset \(S\) containing \(s\) but not \(t\) and compute the forward-arc capacity:

\(S\) \(T = V \setminus S\) Forward arcs crossing Capacity
\(\{s\}\) \(\{a,b,t\}\) \(s{\to}a\ (3),\ s{\to}b\ (4)\) \(7\)
\(\{s,a\}\) \(\{b,t\}\) \(s{\to}b\ (4),\ a{\to}b\ (2),\ a{\to}t\ (2)\) \(8\)
\(\{s,b\}\) \(\{a,t\}\) \(s{\to}a\ (3),\ b{\to}t\ (3)\) \(6\)
\(\{s,a,b\}\) \(\{t\}\) \(a{\to}t\ (2),\ b{\to}t\ (3)\) \(\mathbf{5}\)

Only \(S = \{s, a, b\}\), \(T = \{t\}\) achieves capacity \(5\). This is the unique minimum cut.

The two saturated arcs \(a \to t\) and \(b \to t\) form the bottleneck. By the max-flow min-cut theorem, max flow $= 5 = $ min-cut capacity. \(\checkmark\)

Exercise 3: Flow Conservation Check

Problem. Is the following a valid flow? (Network as in Exercise 1.)

Claimed flow: \(f(s{\to}a)=2\), \(f(s{\to}b)=3\), \(f(a{\to}b)=1\), \(f(a{\to}t)=1\), \(f(b{\to}t)=4\).

Check: (a) capacity constraints, (b) flow conservation at each node, (c) flow value.

Solution.

(a) Capacity constraints:

Arc Flow Capacity Status
\(s \to a\) 2 3 \(\checkmark\)
\(s \to b\) 3 4 \(\checkmark\)
\(a \to b\) 1 2 \(\checkmark\)
\(a \to t\) 1 2 \(\checkmark\)
\(b \to t\) 4 3 VIOLATED (\(4 > 3\))

(b) Flow conservation (divergence \(=\) out \(-\) in at internal nodes):

  • Node \(a\): in \(= 2\), out \(= 1 + 1 = 2\). Divergence \(= 0\). \(\checkmark\)
  • Node \(b\): in \(= 3 + 1 = 4\), out \(= 4\). Divergence \(= 0\). \(\checkmark\) (but \(b \to t\) capacity is violated)

Even if we “fix” \(b \to t = 3\), conservation at \(b\) would break: in \(= 4\), out \(= 3\), divergence \(= 1 \neq 0\). VIOLATED.

(c) Flow value (net flow out of \(s\)): \(f(s{\to}a) + f(s{\to}b) = 2 + 3 = 5\). But this is only meaningful if the flow is feasible, which it is not.

Conclusion. The claimed flow is infeasible: it violates the capacity constraint on arc \(b \to t\) and, consequently, conservation at node \(b\).

Exercise 4: Max-Flow Min-Cut Theorem — True/False

Problem. State whether each claim is True or False and justify briefly.

  1. The maximum flow equals the minimum cut capacity.
  2. If the max flow equals the capacity of a particular cut, that cut is a minimum cut.
  3. Ford-Fulkerson always terminates for integer capacities.
  4. When Ford-Fulkerson terminates, the nodes reachable from \(s\) in the residual graph define the min cut.
  5. Edmonds-Karp (BFS augmentation) has worst-case complexity \(O(VE^2)\).

Solution.

(a) TRUE. This is the max-flow min-cut theorem (Ford–Fulkerson, 1956): for any network, the value of a maximum \(s\)-\(t\) flow equals the capacity of a minimum \(s\)-\(t\) cut.

(b) TRUE. Since max flow \(=\) min-cut capacity (by (a)), any cut whose capacity equals the max-flow value must achieve the minimum — it is a minimum cut by definition.

(c) TRUE. With integer capacities, every augmenting path carries at least 1 unit of flow. The flow value is bounded above by the finite cut capacity, so the algorithm terminates in at most \(C_{\min}\) augmentations, where \(C_{\min}\) is the min-cut capacity.

(d) TRUE. When no augmenting path exists, let \(S\) be the set of nodes reachable from \(s\) in the residual graph and \(T = V \setminus S\). By construction \(t \notin S\). Every arc from \(S\) to \(T\) in the original network is saturated (otherwise a residual forward arc would extend reachability), so the \((S,T)\) cut is saturated and its capacity equals the current flow value, proving it is a minimum cut.

(e) TRUE. Edmonds-Karp uses BFS to always select a shortest (fewest-arc) augmenting path. Each edge becomes a bottleneck at most \(O(V)\) times, and there are \(O(E)\) edges, giving \(O(VE)\) augmentations each taking \(O(E)\) time: total \(O(VE^2)\).

Exercise 5: Min-Cost Flow

Problem. In the network from Exercise 1, add per-unit costs: \(s{\to}a: 1\), \(s{\to}b: 2\), \(a{\to}b: 0\), \(a{\to}t: 3\), \(b{\to}t: 1\).

Find the minimum-cost flow of value 3 (send exactly 3 units from \(s\) to \(t\)).

Solution. We select augmenting paths in order of increasing cost per unit (successive shortest paths by cost).

Step 1. Find the cheapest \(s\)-\(t\) path in the original network:

Path Cost per unit
\(s \to a \to t\) \(1 + 3 = 4\)
\(s \to b \to t\) \(2 + 1 = 3\)
\(s \to a \to b \to t\) \(1 + 0 + 1 = 2\) ← cheapest

Send flow along \(s \to a \to b \to t\): bottleneck \(= \min(3,2,3) = 2\). Send 2 units. Remaining demand \(= 1\).

After 2 units: \(f(s{\to}a)=2\), \(f(a{\to}b)=2\) (saturated), \(f(b{\to}t)=2\). Cost so far \(= 2 \times 2 = 4\).

Step 2. Update residual. Arc \(a \to b\) is saturated; only residual arc \(b \to a\) (backward, cost \(-0 = 0\)) exists there. Remaining cheapest paths:

Path Cost per unit
\(s \to b \to t\) \(2 + 1 = 3\)
\(s \to a \to t\) \(1 + 3 = 4\)

Send 1 unit along \(s \to b \to t\): bottleneck \(= \min(4, 1) = 1\). Send 1 unit. Remaining demand \(= 0\).

After step 2: \(f(s{\to}b)=1\), \(f(b{\to}t)=3\). Cost of this step \(= 1 \times 3 = 3\). Total cost \(= 4 + 3 = 7\).

Optimal solution:

\[ f(s{\to}a) = 2, \quad f(s{\to}b) = 1, \quad f(a{\to}b) = 2, \quad f(b{\to}t) = 3, \quad f(a{\to}t) = 0. \]

Minimum cost \(= 7\).

Verification: flow value \(= f(s{\to}a) + f(s{\to}b) = 2+1=3\) ✓. Conservation at \(a\): in \(=2\), out \(=2+0=2\) ✓. Conservation at \(b\): in \(=2+1=3\), out \(=3\) ✓.

Could we do better? All other 3-unit decompositions:

Decomposition Cost
\(s{\to}a{\to}b{\to}t\ (2) + s{\to}b{\to}t\ (1)\) \(2\cdot2 + 1\cdot3 = \mathbf{7}\)
\(s{\to}b{\to}t\ (3)\) \(3 \cdot 3 = 9\)
\(s{\to}a{\to}t\ (2) + s{\to}b{\to}t\ (1)\) \(2\cdot4 + 1\cdot3 = 11\)
\(s{\to}a{\to}t\ (2) + s{\to}a{\to}b{\to}t\ (1)^*\) requires \(s{\to}a: 3\), cap \(=3\) ✓ but \(a{\to}t: 2\), \(a{\to}b:1\): cost \(2\cdot4+1\cdot2=10\)

Minimum is \(\mathbf{7}\). \(\checkmark\)