Network Flow & Matching

CS F364 — Design & Analysis of Algorithms | Summer 2026

Ford-Fulkerson, Edmonds-Karp, max-flow min-cut, edge-disjoint paths, project selection, flow properties

← Practice

NoteProblem D1

State the Max-Flow Min-Cut Theorem. For a flow network with integer capacities, what does this theorem imply about the value of the maximum flow?

The Max-Flow Min-Cut Theorem states that the value of the maximum flow equals the capacity of the minimum cut. For integer capacities, this implies the maximum flow value is integer and Ford-Fulkerson terminates in finite time with integer flows.

NoteProblem D2

Consider a flow network with vertices s,a,b,t and capacities: s\!\to\!a\,(4), s\!\to\!b\,(3), a\!\to\!b\,(2), a\!\to\!t\,(3), b\!\to\!t\,(4).

  1. Run Ford-Fulkerson starting from zero flow. List all augmenting paths and the flow after each augmentation.
  2. Identify the min-cut. Verify that cut capacity equals max flow value.
  1. Augmenting paths (each adds flow):
    • s \to a \to t: min = min(4,3) = 3. Flow = 3.
    • s \to b \to t: min = min(3,4) = 3. Flow = 6.
    • s \to a \to b \to t: s\to a has 1 remaining, a\to b has 2, b\to t has 1. Flow = 1. Total = 7.
  2. Max flow = 7. Min cut: (\{s\}, \{a,b,t\}) has capacity s\!\to\!a(4) + s\!\to\!b(3) = 7 ✓.
NoteProblem D3

Edge-disjoint paths: Given a directed graph G=(V,E) and two vertices s,t, find the maximum number of pairwise edge-disjoint paths from s to t.

  1. Reduce this to a max-flow problem. (What are the capacities?)
  2. Use the reduction to prove Menger’s Theorem: The maximum number of edge-disjoint s-t paths equals the minimum size of an s-t edge cut.
  1. Set all edge capacities to 1. Max flow = maximum number of edge-disjoint paths.
  2. Menger’s Theorem follows from max-flow min-cut: a cut of capacity k in this network corresponds to a set of k edges whose removal disconnects s from t. The min cut capacity equals the max number of edge-disjoint paths.
NoteProblem D4

Project selection problem: You have n projects. Each project i has a profit p_i (can be negative). There are prerequisites: if you select project i, you must also select certain other projects. Model this as a min-cut problem. Specifically:

  1. Construct a flow network with source s (profits) and sink t (costs).
  2. Prove that the max flow gives the optimal set of projects (maximum total profit while respecting prerequisites).
  3. Run your construction on an example with 4 projects: p = [5, -3, 2, -1], prerequisites: 2 \to 1, 3 \to 2, 4 \to 3.
  1. Create source s and sink t. For each project i with profit p_i > 0, add edge s \to i with capacity p_i. For each project i with p_i < 0, add edge i \to t with capacity -p_i. For each prerequisite i \to j (if i selected then j must be selected), add edge i \to j with capacity \infty.
  2. The min s-t cut gives the optimal set: projects reachable from s in the residual graph after max flow are selected. Maximum profit = total positive profit - min cut capacity.
  3. For the example: p = [5, -3, 2, -1], prerequisites 2\to 1, 3\to 2, 4\to 3. Positive profit: 5+2=7. Edges: s\to 1 (5), s\to 3 (2), 2\to t (3), 4\to t (1), 2\to 1 (\infty), 3\to 2 (\infty), 4\to 3 (\infty). Min cut: (\{s,1,3\}, \{2,4,t\}) has capacity 3+1=4 (edges 2\to t and 4\to t). Selected: projects 1 and 3. Total profit: 7-4=3.
NoteProblem D5

Decide whether each statement is true or false. Justify with a proof or counterexample.

  1. If f is a maximum s-t flow in G, then f saturates every edge out of s (i.e., f_e = c_e for all edges (s,u)).
  2. Let (A,B) be a minimum s-t cut in G with capacities c_e. If we add 1 to every capacity, then (A,B) is still a minimum s-t cut.

  1. False. A max flow need not saturate all edges leaving s. Example: s \to a (cap 5), s \to b (cap 5), a \to t (cap 1), b \to t (cap 1). Max flow = 2 (1 unit through each path). Neither s\to a nor s\to b is saturated — both carry only 1 of their 5-unit capacity.

  2. False. Adding a constant to every capacity changes the number of crossing edges per cut, which can alter which cut is minimal. Example: s \to a (cap 100), and a \to x_i (cap 1), x_i \to t (cap 1) for i=1,\dots,60. Original min cut = (\{s,a\}, \{x_1,\dots,x_{60},t\}) with capacity 60 (60 edges a\to x_i). Cut (\{s\}, \{a,x_1,\dots,x_{60},t\}) has capacity 100. After adding 1 to all edges: s\to a becomes 101; each a\to x_i, x_i\to t becomes 2. Now (\{s,a\}, \dots) has capacity 60 \times 2 = 120, while (\{s\}, \dots) has capacity 101 — so the min cut changes!