Definitions (all relative to the current residual graph G_f)

  • Level ℓ(v) = shortest-path (unweighted) distance from s to v in G_f 31:11, 34:02.
  • An edge (u, v) is admissible iff ℓ(v) = ℓ(u) + 1, i.e. it lies on a shortest path from s 34:02.
  • A path is admissible iff all its edges are admissible 34:45.
  • The level graph L = the subgraph of admissible edges (only those with positive residual capacity) 43:19, 52:47.
  • A blocking flow is an admissible flow f — it decomposes into admissible augmenting s–t paths — such that every admissible s–t path has at least one edge saturated by f 35:48.
  • Admissibility is not stable: it is defined against the residual graph of the moment, and the residual graph changes every augmentation step 45:45.
  • Attribution: blocking flows are credited to Dinitz, sometime in the 1970s (the lecturer states it from memory) 34:45, 35:48.

Structure of the level graph

  • Edges of L only connect adjacent layers 52:47.
  • Forward layer-skipping edges cannot exist — such an edge would contradict the shortest-path distances 54:07.
  • What can exist in G_f but not in L: backward edges (possibly skipping layers) and edges within a level 54:34, 55:54.
  • Consequence used later: L is a DAG, so a DFS on it cannot hit cycles 1:11:42, 1:12:23.

Blocking flow ≠ max flow

  • A max flow is a blocking flow, but the converse fails — the lecture works two counterexamples with the class 37:58, 38:30.
  • Counterexample 1 (student-proposed, non-unit capacities): capacities c(s,u) = 2, c(u,v) = 1, c(v,t) = 2, everything else 1 — the flow through u → v is blocking but not maximum 39:57, 40:24.
  • Counterexample 2 (all unit capacities): one flow path can block two otherwise-disjoint augmenting paths; the max flow would send one unit along each, but the blocking flow saturates the shared edge 40:24, 41:16, 41:33.
  • Non-admissible edges are simply excluded: in the toy residual graph drawn on the board, one edge is not admissible and so plays no part 37:27, 37:58, 39:26.

Worked residual-graph example

  • After augmenting along a blocking flow, saturated edges reverse; in the board example the new residual graph has exactly one s–t path, of length 5, so the new level graph is just that path s → a → b → c → d → t 47:00, 48:04, 48:40, 49:09.