Back to course

Exercise 6

Flow Theory

Maximum FlowFlow-Matching ReductionsMedium Difficulty

Exam Format & Expectations

Flow Theory questions typically involve:

  1. Max-flow min-cut theorem - Find minimum cut given maximum flow
  2. Flow conservation - Verify or compute flows at vertices
  3. Reduction to matching - Convert problems to bipartite matching
  4. Prove flow properties - Value, feasibility, optimality

Past Exam Example: Finding Minimum Cut (2024)

Problem:

Given a flow network with maximum flow value 15. The final residual network Gf* is:

s → a: 0 (saturated)
s → b: 3
a → c: 2
b → c: 0 (saturated)
b → d: 4
c → t: 0 (saturated)
d → t: 1
(Plus backward edges)

Find a minimum cut (S, T) and verify its capacity equals 15.

Full Solution(10/10)

Step 1: Find reachable vertices from s in Gf*:

• From s: Can reach b (residual capacity 3)

• From b: Can reach d (residual capacity 4)

• Cannot reach a (no edge from s)

• Cannot reach c (no edge from b)

• Cannot reach t (no path)

Step 2: Define the cut:

S = { s, b, d } (reachable from s)

T = { a, c, t } (not reachable)

Step 3: Find edges crossing the cut (S → T):

• (s, a) with capacity c(s,a)

• (b, c) with capacity c(b,c)

• (d, t) with capacity c(d,t)

Step 4: Verify these edges are saturated:

Since residual capacity is 0 for edges crossing S → T,

they must be saturated in the maximum flow.

Step 5: Calculate cut capacity:

c(S,T) = c(s,a) + c(b,c) + c(d,t) = 15

By max-flow min-cut theorem: max flow = min cut = 15 ✓

Example: Reduction to Bipartite Matching

Problem: Task Assignment

n workers and m tasks. Worker i can perform task j if (i,j) ∈ E. Each worker can do at most k tasks. Each task needs exactly one worker. Maximize number of completed tasks.

Show how to reduce this to a max-flow problem.

Full Solution(10/10)

Construction:

  1. Create vertices:
    • • Source s and sink t
    • • Vertex wi for each worker i
    • • Vertex tj for each task j
  2. Add edges:
    • • (s, wi) with capacity k for each worker i
    • • (wi, tj) with capacity 1 if (i,j) ∈ E
    • • (tj, t) with capacity 1 for each task j
  3. Correspondence:

    Maximum flow = maximum number of tasks assigned

Why it works:

  • • Edge (s, wi) capacity k limits worker i to k tasks
  • • Edge (tj, t) capacity 1 ensures task j assigned once
  • • Unit capacities on matching edges ensure integral flow

Key Theorems to Remember

Max-Flow Min-Cut Theorem

max { |f| : f is a flow } = min { c(S,T) : (S,T) is a cut }

The maximum flow value equals the capacity of the minimum cut.

Flow Conservation

For all v ≠ s,t:

Σu f(u,v) = Σw f(v,w)

Inflow equals outflow at every internal vertex.

Integrality Theorem

If all capacities are integers, then there exists an integral maximum flow. Ford-Fulkerson will find it.

Common Reduction Patterns

Vertex Capacities

To model vertex capacity c(v):

  1. 1. Split v into vin and vout
  2. 2. Add edge (vin, vout) with capacity c(v)
  3. 3. Redirect all incoming edges to vin
  4. 4. Redirect all outgoing edges from vout

Multiple Sources/Sinks

For multiple sources s1,...,sk:

  1. 1. Add super-source s
  2. 2. Add edges (s, si) with capacity ∞
  3. 3. Similarly for multiple sinks
Previous: Shortest PathsNext: NP-Complexity