---
title: Max-Flow Min-Cut and Applications
module: Graphs
moduleNumber: 6
lessonNumber: 9
order: 609
summary: |
  Why is the flow found when no augmenting path remains actually optimal? The
  answer is a duality theorem: the maximum flow equals the minimum cut. We prove
  it, read the minimum cut off the final residual graph, then derive bipartite
  matching and a catalog of modeling reductions from the flow
  abstraction — before touching the modern algorithms that supersede
  Edmonds-Karp.
topics: [Network Flow, Min Cut, Bipartite Matching]
sources:
  - book: CLRS
    ref: "Ch. 26 — Maximum Flow"
  - book: Erickson
    ref: "Ch. 11 — Applications of Maximum Flow"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms"
practice:
  - title: 'Is Graph Bipartite?'
    slug: is-graph-bipartite
    difficulty: Medium
  - title: 'Maximum Students Taking Exam'
    slug: maximum-students-taking-exam
    difficulty: Hard
---

This builds on [Network Flow](/algorithms/graphs/network-flow), which developed flow networks, the residual graph, and the augmenting-path algorithms. We pick up exactly where that lesson halted: with a flow whose residual graph has no $s$–$t$ path, and the question of _why_ that flow is provably maximum.

## The max-flow min-cut theorem

When does Ford-Fulkerson stop, and _why is the result optimal_? The answer is
a duality theorem linking flow to **cuts**.[^clrs-mincut]

> **Definition (Cut).** A cut is a partition $V = S \cup T$ with $S \ne \emptyset$, $T \ne
> \emptyset$, $S \cap T = \emptyset$ (write it $(S, T)$; fixing $S$ forces
> $T = \bar S$). It is an **$s$–$t$ cut** when $s \in S$ and $t \in T$. Its
> **capacity** is the total capacity of edges crossing _forward_, from $S$ to
> $T$:
> $$
> c(S, T) = \sum_{u \in S} \sum_{v \in T} c_{uv}
> \qquad (\text{convention: } c_{uv} = 0 \text{ if } (u, v) \notin E).
> $$

The dual view is a **minimum-cut** problem: an adversary wants to cut a cheap set
of edges so that _no_ $s$–$t$ flow can get through. The two problems turn out to
be the same problem.

$$
% caption: A flow network with an $s$-$t$ cut separating $S$ from $T$, the crossing
%          forward edges drawn dashed in red.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[vtx] (s) {$s$};
  \node[vtx] (a) [above right=6mm and 14mm of s] {$a$};
  \node[vtx] (g) [below right=6mm and 14mm of s] {$g$};
  \node[vtx] (b) [right=16mm of a] {$b$};
  \node[vtx] (d) [right=20mm of b] {$d$};
  \node[vtx] (h) [below=14mm of d] {$h$};
  \node[vtx] (t) [below right=2mm and 16mm of d] {$t$};
  \draw[->] (s) -- node[fl, above left]{$3$} (a);
  \draw[->] (s) -- node[fl, below left]{$10$} (g);
  \draw[->] (a) -- node[fl, above]{$10$} (b);
  \draw[->,>=Stealth, red, very thick, dashed] (b) -- node[fl, above]{$5$} (d);
  \draw[->] (g) -- node[fl, pos=0.45]{$15$} (b);
  \draw[->,>=Stealth, red, very thick, dashed] (g) -- node[fl, below]{$10$} (h);
  \draw[->] (d) -- node[fl]{$15$} (t);
  \draw[->] (d) -- node[fl, pos=0.45]{$10$} (h);
  \draw[->] (h) -- node[fl, below right]{$20$} (t);
  % S = the source side {s,a,b,g}; a clean rectangle whose right edge both cut edges cross
  \draw[dashed, draw=acc]
        ($(s)+(-0.7,2.0)$) rectangle ($(b)+(0.9,-3.2)$);
  \node[acc, font=\scriptsize] at ($(s)+(0.1,1.3)$) {$S$};
  \node[font=\scriptsize] at ($(t)+(0.6,1.0)$) {$T$};
\end{tikzpicture}
$$

> **Theorem (Max-flow min-cut).** In any flow network $G = (V, E, c)$ with
> $s \ne t$,
> $$
> \max_{\substack{f \text{ feasible}}} \abs{f}
>   \;=\; \min_{\substack{(S, T)\ s\text{–}t\text{ cut}}} c(S, T).
> $$

> **Proof.** Two directions.
>
> **Easy direction (weak duality):** _every_ feasible flow $f$ and _every_ $s$–$t$
> cut $(S, T)$ satisfy $\abs{f} \le c(S, T)$. We compute $\abs{f}$ by summing
> $\partial f$ over all of $S$, where conservation makes the interior terms vanish,
> leaving only $\partial f(s)$:
>
> $$
> \begin{aligned}
> \abs{f}
>   &= \partial f(s)
>    = \sum_{x \in S} \partial f(x) && \text{(conservation kills $x \ne s$)}\\
>   &= \sum_{x \in S}\parens{\sum_{(x, w) \in E} f_{xw} - \sum_{(u, x) \in E} f_{ux}}\\
>   &= \sum_{x \in S}\sum_{\substack{(x, w) \in E \\ w \in T}} f_{xw}
>      \;-\; \sum_{x \in S}\sum_{\substack{(u, x) \in E \\ u \in T}} f_{ux}
>      && \text{(edges inside $S$ cancel)}\\
>   &\le \sum_{x \in S}\sum_{\substack{(x, w) \in E \\ w \in T}} f_{xw}
>      && \text{(drop the non-negative subtrahend)}\\
>   &\le \sum_{x \in S}\sum_{\substack{(x, w) \in E \\ w \in T}} c_{xw}
>    = c(S, T). && \text{(capacity constraint)}
> \end{aligned}
> $$
>
> So $\max \abs{f} \le \min c(S, T)$; flow is bounded by the narrowest cut.
>
> **Hard direction:** there _exist_ a flow $f^\ast$ and an $s$–$t$ cut $(S^\ast, T^\ast)$
> with $\abs{f^\ast} = c(S^\ast, T^\ast)$. Take $f^\ast$ to be a **maximum** flow. If $G_{f^\ast}$
> had an augmenting path, the augmentation lemma would yield a larger flow, a
> contradiction. Therefore **$t$ is not reachable from $s$ in $G_{f^\ast}$**. Define
> the reachable set and its complement:
>
> $$
> S^\ast := \set{x \in V : x \text{ is reachable from } s \text{ in } G_{f^\ast}},
> \qquad T^\ast := V \setminus S^\ast.
> $$
>
> Then $s \in S^\ast$ and $t \in T^\ast$, so $(S^\ast, T^\ast)$ is a genuine $s$–$t$ cut. Now
> the two boundary observations:
>
> - **Forward edges are saturated.** Every $(u, v) \in E$ with $u \in S^\ast$,
>   $v \in T^\ast$ has $f^\ast_{uv} = c_{uv}$; otherwise it would contribute a forward
>   residual edge, making $v$ reachable from $s$, so $v \in S^\ast$, a contradiction.
> - **Backward edges are empty.** Every $(v, u) \in E$ with $v \in T^\ast$,
>   $u \in S^\ast$ has $f^\ast_{vu} = 0$; otherwise it would contribute a _reverse_
>   residual edge $(u, v) \in G_{f^\ast}$, again making $v$ reachable.
>
> These are the two inequalities that were slack in the easy direction. With
> forward edges saturated ($f = c$) and backward edges unused ($f = 0$), both "$\le$"
> steps become equalities, so $\abs{f^\ast} = c(S^\ast, T^\ast)$. Combined with weak duality,
> $f^\ast$ is a maximum flow and $(S^\ast, T^\ast)$ is a minimum cut. $\qed$

Because the hard direction shows the converse of the augmentation lemma, we get
the promised three-way equivalence.

> **Theorem (Three equivalent statements).** For a feasible $s$–$t$ flow $f$
> in $G$, the following are equivalent:
>
> 1. $f$ is a maximum flow;
> 2. the residual graph $G_f$ contains no augmenting path;
> 3. $\abs{f} = c(S, T)$ for some $s$–$t$ cut $(S, T)$.
>
> ($1 \Rightarrow 2$ is the augmentation lemma read contrapositively;
> $2 \Rightarrow 3$ is the reachable-set construction in the hard direction;
> $3 \Rightarrow 1$ is weak duality: no flow can exceed any cut it equals.)

This is also why $\textsc{Ford-Fulkerson}$ is correct: it halts exactly when
$G_f$ has no $s$–$t$ path, which is precisely when $f$ is maximum. Better, the
halting state yields the minimum cut for free: the proof's $S^\ast$ is just
the set of vertices BFS reaches from $s$ in the final residual graph, so one
extra $O(m)$ traversal after the last augmentation outputs a minimum cut.

### The min cut of the worked run

Return to the six-vertex network. Round 4's BFS reached exactly
$S^\ast = \set{s, a, c, d}$, so the theorem says the crossing edges form a
minimum cut. Two edges cross forward: $a \to b$ (capacity $5$) and $d \to t$
(capacity $8$), so

$$
c(S^\ast, T^\ast) \;=\; c_{ab} + c_{dt} \;=\; 5 + 8 \;=\; 13 \;=\; \abs{f^\ast},
$$

matching the flow value exactly — the certificate that round 3's flow is
maximum. Both boundary observations from the proof are visible: the two
crossing edges are saturated ($f_{ab} = 5 = c_{ab}$, $f_{dt} = 8 = c_{dt}$),
and no edge crosses backward from $T^\ast$ into $S^\ast$ at all.

$$
% caption: The maximum flow of the worked run, edges labeled flow over capacity, with the
%          minimum cut $S^* = \{s, a, c, d\}$ (region $S$) found by the final BFS. The crossing edges
%          $a \to b$ and $d \to t$ (dashed red) are saturated and their capacities sum to
%          $5 + 8 = 13 = |f^*|$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  fl/.style={font=\scriptsize, fill=white, inner sep=1.6pt},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[vtx] (s) at (0,0) {$s$};
  \node[vtx] (a) at (2,1.1) {$a$};
  \node[vtx] (c) at (2,-1.1) {$c$};
  \node[vtx] (b) at (4.4,1.1) {$b$};
  \node[vtx] (d) at (4.4,-1.1) {$d$};
  \node[vtx] (t) at (6.4,0) {$t$};
  \draw[->] (s) -- node[fl, above left]{8/8} (a);
  \draw[->] (s) -- node[fl, below left]{5/6} (c);
  \draw[->, red!75!black, very thick, dashed] (a) -- node[fl, above]{5/5} (b);
  \draw[->] (a) -- node[fl, pos=0.38]{3/3} (d);
  \draw[->] (c) -- node[fl, below]{5/7} (d);
  \draw[->] (b) -- node[fl, above right]{5/6} (t);
  \draw[->, red!75!black, very thick, dashed] (d) -- node[fl, below right, pos=0.62]{8/8} (t);
  \draw[dashed, acc, thick] plot[smooth]
    coordinates {(3.6,2.05) (3.7,1.2) (4.0,0.3) (5.0,-0.45) (5.6,-1.5) (5.7,-2.1)};
  \node[acc, font=\scriptsize] at (2.9,1.95) {$S$};
  \node[font=\scriptsize] at (4.35,1.95) {$T$};
\end{tikzpicture}
$$

Two easy misreadings to avoid. First, the minimum cut is **not** "all
saturated edges": $s \to a$ is saturated here yet lies entirely inside $S^\ast$
and crosses nothing. Saturation is _necessary_ for a forward crossing edge of
a minimum cut, not _sufficient_ for membership. Second, cut capacity counts
**forward edges only**; if some edge ran from $T^\ast$ back into $S^\ast$, its
capacity would not be charged (though a maximum flow must leave it empty).

::impl{algo="min_cut"}

## Application: bipartite matching

The payoff of the flow abstraction is that other problems reduce to it.[^skiena-flow]
A useful rule of thumb: _whenever a graph problem looks for paths or cycles
under some per-edge or per-vertex budget constraint, reach for max-flow as a
subroutine_, and many non-graph problems (task assignment, base-station
connection, workshop scheduling) yield to it too once you find the right network.

Consider **bipartite matching**: a set $L$ of applicants, a set $R$ of jobs, and
an edge for each applicant qualified for a job (edge $a_i \to r_j$ iff
$A[i][j] = \text{true}$). A **matching** pairs applicants to jobs with no one used
twice; we want a **maximum matching**.

Build a flow network: add a source $s$ with a unit-capacity edge to every
applicant, add a sink $t$ with a unit-capacity edge from every job, and orient
each qualification edge from $L$ to $R$ with capacity $1$.

$$
% caption: Bipartite matching modeled as flow, with source $s$, applicants, jobs, and sink
%          $t$ joined by unit-capacity edges.
\begin{tikzpicture}[every node/.style={circle, draw, minimum size=7mm, font=\small},
  >={Stealth[round]}]
  \node (s) at (0,0) {$s$};
  \node (l1) at (2,1.2) {$a_1$};
  \node (l2) at (2,0) {$a_2$};
  \node (l3) at (2,-1.2) {$a_3$};
  \node (r1) at (4,1.2) {$r_1$};
  \node (r2) at (4,0) {$r_2$};
  \node (r3) at (4,-1.2) {$r_3$};
  \node (t) at (6,0) {$t$};
  \draw[->] (s) -- (l1);
  \draw[->] (s) -- (l2);
  \draw[->] (s) -- (l3);
  \draw[->] (l1) -- (r1);
  \draw[->] (l1) -- (r2);
  \draw[->] (l2) -- (r2);
  \draw[->] (l3) -- (r2);
  \draw[->] (l3) -- (r3);
  \draw[->] (r1) -- (t);
  \draw[->] (r2) -- (t);
  \draw[->] (r3) -- (t);
\end{tikzpicture}
$$

The reduction works because of an exact correspondence in both directions: if
$k$ tasks _can_ be assigned, those $k$ disjoint $s \to a \to r \to t$ routes
form a flow of value $k$ (easy); conversely, if the max-flow value is $k$, then
$k$ tasks can be assigned (less obvious, since it needs integrality).

> **Theorem (Integrality).** If all edge capacities are integers, then some maximum
> flow is _integral_ (every $f_{uv} \in \mathbb{Z}$), and $\textsc{Ford-Fulkerson}$
> /$\textsc{Edmonds-Karp}$ finds it. Such an integral flow decomposes into a
> collection of **path flows** from $s$ to $t$.

> **Proof sketch.** Induction on the augmentations. The zero flow is integral.
> If the current flow is integral, every residual capacity $c^f_e$ is either
> $c_e - f_e$ or $f_e$, both integers, so the bottleneck — a minimum of
> integers — is an integer, and augmenting adds or subtracts it from integer
> flow values. The invariant survives every iteration, and termination is
> guaranteed because each augmentation raises the value by at least $1$. For
> the decomposition, repeatedly trace a path of flow-carrying edges from $s$
> to $t$ (conservation guarantees each visited interior vertex has an outgoing
> flow edge), subtract the minimum flow along it, and recurse; each pass
> zeroes out at least one edge, so at most $m$ paths result. $\qed$

The word "some" is doing work in the statement: fractional maximum flows also
exist (split each unit half-and-half across two routes), but at least one
_integral_ optimum always exists, and the augmenting-path algorithms never
create fractions they were not given. Here every capacity is $1$, so the
maximum flow is $0$/$1$ on every edge. Its
path-flow decomposition is a set of vertex-disjoint $s \to a \to r \to t$
routes; reading off the middle $a \to r$ edge of each gives a matching, and the
_value_ of the max flow equals the _size_ of the maximum matching. So one run of
$\textsc{Edmonds-Karp}$ solves bipartite matching.

For the network above, the integral max flow saturates three vertex-disjoint
routes, shown in blue: $a_1 \to r_1$, $a_2 \to r_2$, $a_3 \to r_3$. The
flow value is $3$, so the maximum matching has size $3$ — every applicant is
placed:

$$
% caption: The integral max flow of value $3$ (blue) decomposes into three vertex-disjoint
%          routes; the middle edges $a_1 r_1, a_2 r_2, a_3 r_3$ are the maximum
%          matching.
\begin{tikzpicture}[every node/.style={circle, draw, minimum size=7mm, font=\small},
  >={Stealth[round]},
  use/.style={->, line width=1.4pt, draw=acc},
  off/.style={->, draw=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node (s) at (0,0) {$s$};
  \node (l1) at (2,1.2) {$a_1$};
  \node (l2) at (2,0) {$a_2$};
  \node (l3) at (2,-1.2) {$a_3$};
  \node (r1) at (4,1.2) {$r_1$};
  \node (r2) at (4,0) {$r_2$};
  \node (r3) at (4,-1.2) {$r_3$};
  \node (t) at (6,0) {$t$};
  % source/sink edges carrying flow
  \draw[use] (s) -- (l1);
  \draw[use] (s) -- (l2);
  \draw[use] (s) -- (l3);
  % qualification edges: matched (blue) vs unused (faint)
  \draw[use] (l1) -- (r1);   % matched
  \draw[off] (l1) -- (r2);   % unused alternative
  \draw[use] (l2) -- (r2);   % matched (l2's only option)
  \draw[off] (l3) -- (r2);   % unused alternative
  \draw[use] (l3) -- (r3);   % matched
  \draw[use] (r1) -- (t);
  \draw[use] (r2) -- (t);
  \draw[use] (r3) -- (t);
\end{tikzpicture}
$$
This is the template for
many reductions (assignment, base-station connection, workshop scheduling,
vertex-disjoint paths), all of which become "build a network, compute max flow,
read off an integral solution."

::impl{algo="bipartite_matching"}

## Modeling tricks and pitfalls

Real problems rarely arrive in the exact shape the definitions demand. A small
kit of standard transformations, plus the failure modes worth knowing:

- **Multiple sources or sinks.** Add a supersource $s'$ with an edge
  $s' \to s_i$ of capacity $\sum_e c_e$ (effectively unlimited) to each real
  source, and symmetrically a supersink. Max flow in the new network equals
  the total max flow of the old one.
- **Vertex capacities.** If a vertex $v$ may carry at most $k$ units, split it
  into $v_{\text{in}} \to v_{\text{out}}$ joined by an edge of capacity $k$;
  route all former in-edges into $v_{\text{in}}$ and all out-edges out of
  $v_{\text{out}}$. Vertex-disjoint path problems use this with $k = 1$.
- **Undirected edges.** Replace $\set{u, v}$ of capacity $c$ with directed
  edges $(u, v)$ and $(v, u)$, each of capacity $c$, then apply the
  anti-parallel splitting trick if the representation requires it.
- **Anti-parallel pairs.** When both $(u, v)$ and $(v, u)$ appear, subdivide
  one of them through a dummy vertex so residual reverse edges stay
  unambiguous.

The failure modes:

- **Irrational capacities break raw Ford-Fulkerson.** With arbitrary path
  choice the method is only guaranteed to terminate when capacities are
  integers (or rationals, which scale to integers). On irrational capacities
  there are networks where it runs forever, and worse: the flow values
  converge to a limit _strictly below_ the maximum, so even "run it long
  enough" fails. $\textsc{Edmonds-Karp}$ is immune; its $O(m^2 n)$ bound never
  mentions capacities.
- **Pseudo-polynomial blowup.** $O(m \abs{f^\ast})$ is fine when capacities are
  small and disastrous when they are large; the two-path network with the
  unit middle edge realizes the worst case. If capacities can be big, insist
  on the BFS rule.
- **Forgetting integrality when reading off answers.** Reductions like
  matching need an _integral_ flow to decode; the integrality theorem
  guarantees the augmenting-path algorithms deliver one, but a fractional
  solution from some other solver (say, a linear-programming relaxation)
  would need rounding first.

As defaults: $\textsc{Edmonds-Karp}$ is the implementation to write, $O(mn)$
(Orlin) is the bound to quote for a black-box subroutine, and for unit-capacity
networks such as [bipartite matching](/algorithms/graphs/bipartite-matching)
specialized bounds are far better than the generic ones.

## Faster max-flow

$\textsc{Edmonds-Karp}$ is the version to _understand_, but it is nowhere near the fastest known. Its $O(VE^2)$ bound has been beaten repeatedly, and the ideas behind the faster methods are worth a paragraph each.

**Dinic's algorithm (1970).** Dinic's insight is to stop augmenting one path at a time.[^dinic] From the current flow, build the **level graph** by one BFS from $s$ — keep only residual edges that go from level $\ell$ to level $\ell+1$ — then push a **blocking flow** through it (a flow that saturates at least one edge on every remaining $s$–$t$ path in the level graph). A single blocking flow can be found in $O(VE)$ with DFS, and each one strictly increases the shortest-path distance $\delta_f(t)$, so there are at most $V-1$ phases. That gives $O(V^2 E)$ overall — already better than Edmonds-Karp on dense graphs, and $O(E\sqrt{V})$ on the unit-capacity networks that model [bipartite matching](/algorithms/graphs/bipartite-matching), which is the bound the Hopcroft-Karp matching algorithm realizes directly.

$$
% caption: Dinic's level graph: one BFS layers the residual vertices by distance from $s$;
%          a blocking flow is pushed using only the forward edges (solid) between
%          consecutive layers. Cross- and back-edges (dashed) are ignored this phase.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  lbl/.style={font=\scriptsize, draw=none},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[vtx] (s) at (0,0) {$s$};
  \node[vtx] (a) at (2.2,1.1) {$a$};
  \node[vtx] (b) at (2.2,-1.1) {$b$};
  \node[vtx] (c) at (4.4,1.1) {$c$};
  \node[vtx] (d) at (4.4,-1.1) {$d$};
  \node[vtx] (t) at (6.6,0) {$t$};
  \draw[->, acc, thick] (s) -- (a);
  \draw[->, acc, thick] (s) -- (b);
  \draw[->, acc, thick] (a) -- (c);
  \draw[->, acc, thick] (b) -- (d);
  \draw[->, acc, thick] (b) -- (c);
  \draw[->, acc, thick] (c) -- (t);
  \draw[->, acc, thick] (d) -- (t);
  \draw[->, dashed, black] (a) to[bend left=20] (b); % same-level: ignored
  \draw[->, dashed, black] (c) to[bend left=20] (d); % same-level: ignored
  \node[lbl] at (0,-1.7) {level 0};
  \node[lbl] at (2.2,-2.1) {level 1};
  \node[lbl] at (4.4,-2.1) {level 2};
  \node[lbl] at (6.6,-1.7) {level 3};
\end{tikzpicture}
$$

**Push-relabel (Goldberg-Tarjan, 1988).** Rather than maintaining a valid flow and augmenting along whole paths, push-relabel maintains a **preflow** (conservation may be violated by _excess_ piling up at interior vertices) and a **height** label on each vertex.[^goldberg] It repeatedly _pushes_ excess downhill from a higher vertex to a lower neighbor with residual room, and _relabels_ (raises the height of) a vertex with excess but no downhill neighbor. When no vertex except $t$ has excess, the preflow is a maximum flow. The generic rule runs in $O(V^2 E)$; the **highest-label** and **FIFO** selection rules improve this to $O(V^3)$ and $O(V^2\sqrt E)$, and in practice push-relabel is often the fastest general-purpose method. It is the algorithm most industrial max-flow codes actually implement.

**The current frontier.** For decades the record for sparse graphs was Orlin's $O(VE)$ algorithm (2013), which is the bound to quote when you use max-flow as a black-box subroutine.[^orlin] In 2022 Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva announced a max-flow algorithm running in _almost-linear_ time $m^{1+o(1)}$, resolving a question open since Ford and Fulkerson by routing flow through fast solvers for the underlying convex program.[^almostlinear] It is a landmark theoretical result, not something you would code by hand — but it settles the asymptotics: max-flow is, up to sub-polynomial factors, as cheap as reading the graph.

The practical takeaway is unchanged. Write $\textsc{Edmonds-Karp}$ when you need something correct and simple; reach for push-relabel or a library routine when max-flow sits on the hot path; and quote $O(VE)$ (Orlin) or $m^{1+o(1)}$ (Chen et al.) when you only need the abstraction's cost, not its code.

## Takeaways

- A **flow network** routes flow from $s$ to $t$ under **capacity** and
  **conservation** ($\partial f(v) = 0$) constraints; the value $\abs{f} =
  \partial f(s) = -\partial f(t)$ is what we maximize.
- The **residual graph** $G_f$ adds **reverse** edges (capacity $f_{uv}$) that let
  us _undo_ flow; the **augmentation lemma** proves pushing $k$ along any $s$–$t$
  path of $G_f$ yields a feasible flow of value $\abs{f} + k$.
- $\textsc{Ford-Fulkerson}$ augments until $G_f$ has no $s$–$t$ path; with integer
  capacities it runs in $O(m\abs{f^\ast}) = O(m^2 C)$ (pseudo-polynomial), and on
  irrational capacities it may fail to terminate at all.
- $\textsc{Edmonds-Karp}$'s BFS choice makes it $O(m^2 n)$, capacity-independent:
  BFS distances never decrease, so each edge is critical $O(n)$ times and
  $O(mn)$ augmentations suffice.
- The **max-flow min-cut theorem** (max flow $=$ min cut) gives a three-way
  equivalence: $f$ is maximum $\iff$ $G_f$ has no augmenting path $\iff$
  $\abs{f} = c(S, T)$ for some cut. The hard direction builds the cut from the set
  reachable from $s$ in $G_{f^\ast}$.
- By the **integrality theorem**, an all-integer network has an integral max flow
  that decomposes into **path flows**; **bipartite matching** is the canonical
  unit-capacity instance among flow's many applications.

[^clrs-mincut]: **CLRS**, Ch. 26 — Maximum Flow — the max-flow min-cut theorem equating maximum flow with minimum cut.
[^skiena-flow]: **Skiena**, §6 — Weighted Graph Algorithms — modeling problems such as bipartite matching as max-flow instances.
[^dinic]: **Dinic, E. A.** (1970), "Algorithm for solution of a problem of maximum flow in networks with power estimation," _Soviet Math. Doklady_ 11, 1277–1280 — blocking flows on the level graph, $O(V^2 E)$.
[^goldberg]: **Goldberg, A. V. & Tarjan, R. E.** (1988), "A new approach to the maximum-flow problem," _Journal of the ACM_ 35(4), 921–940 — the push-relabel method.
[^orlin]: **Orlin, J. B.** (2013), "Max flows in $O(nm)$ time, or better," _Proc. STOC 2013_, 765–774 — max-flow in $O(VE)$ on sparse graphs.
[^almostlinear]: **Chen, Kyng, Liu, Peng, Probst Gutenberg & Sachdeva** (2022), "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time," _Proc. FOCS 2022_ — max-flow in $m^{1+o(1)}$ time.