Max-Flow Min-Cut and Applications

This builds on 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.¹

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.

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

This is also why $\text{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 }=\left\{s,a,c,d\right\}$, 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

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.

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).

from __future__ import annotations

from collections import deque
from collections.abc import Hashable
from typing import Generic, NamedTuple, TypeVar

from edmonds_karp import edmonds_karp
from flow_network import FlowEdge, FlowNetwork, FlowVertex

Label = TypeVar("Label", bound=Hashable)

class Cut(NamedTuple, Generic[Label]):
  """
    A minimum s-t cut: the source side `source_set`, the sink side\n
    `sink_set`, the saturated forward edges `crossing` from S to T, and\n
    the total `capacity` of those edges (equal to the maximum flow value).\n
  """
  source_set: set[Label]
  sink_set: set[Label]
  crossing: list[FlowEdge[Label]]
  capacity: float

def _reachable_in_residual(
  network: FlowNetwork[Label],
  source: FlowVertex[Label],
) -> set[Label]:
  """
    Every vertex label reachable from `source` along edges that still have\n
    spare residual capacity — the set S of the min cut.\n
  """
  reachable: set[Label] = {source.label}
  queue: deque[FlowVertex[Label]] = deque([source])

  # bfs along edges with spare residual capacity.
  while queue:
    current: FlowVertex[Label] = queue.popleft()
    for edge in current.outgoing:
      neighbor: FlowVertex[Label] = edge.target
      if edge.residual_capacity() > 0 and neighbor.label not in reachable:
        reachable.add(neighbor.label)
        queue.append(neighbor)

  return reachable

def min_cut(
  network: FlowNetwork[Label],
  source_label: Label,
  sink_label: Label,
) -> Cut[Label]:
  """
    The minimum s-t cut of `network`. Runs Edmonds-Karp to a maximum flow\n
    (mutating edge flows in place), then reads off the cut from the\n
    residual reachable set. The returned capacity equals the max-flow value.\n
  """
  network.reset_flow()
  edmonds_karp(network, source_label, sink_label)

  # edmonds_karp has already ensured the terminal exists; get-or-create
  # keeps this robust if called on a network with an isolated source.
  source: FlowVertex[Label] = network.add_vertex(source_label)
  source_set: set[Label] = _reachable_in_residual(network, source)
  sink_set: set[Label] = {
    vertex.label for vertex in network if vertex.label not in source_set
  }

  # forward edges leaving S for T are exactly the saturated cut edges.
  crossing: list[FlowEdge[Label]] = [
    edge
    for edge in network.edges()
    if edge.source.label in source_set and edge.target.label in sink_set
  ]
  capacity: float = sum(edge.capacity for edge in crossing)

  return Cut(
    source_set=source_set,
    sink_set=sink_set,
    crossing=crossing,
    capacity=capacity,
  )

Application: bipartite matching

The payoff of the flow abstraction is that other problems reduce to it.² 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$.

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).

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 $\text{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:

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.

from collections.abc import Hashable, Iterable
from typing import TypeVar

from edmonds_karp import edmonds_karp
from flow_network import FlowEdge, FlowNetwork

Applicant = TypeVar("Applicant", bound=Hashable)
Job = TypeVar("Job", bound=Hashable)

# network labels are tagged tuples so the two sides (and the synthetic
# terminals) never collide even when applicants and jobs share raw values.
_Label = tuple[Hashable, ...]
_SOURCE: _Label = ("__source__",)
_SINK: _Label = ("__sink__",)

def maximum_bipartite_matching(
  qualifications: Iterable[tuple[Applicant, Job]],
) -> dict[Applicant, Job]:
  """
    A maximum matching of applicants to jobs given the allowed\n
    `qualifications` (applicant, job) pairs, returned as a dict mapping each\n
    matched applicant to its assigned job. No applicant or job appears\n
    twice; the dict's size is the maximum matching size.\n
    Applicant and job labels are tagged ("L", x) / ("R", y) inside the\n
    network so the two sides never collide even if they share raw values.\n
  """
  edges: list[tuple[Applicant, Job]] = list(qualifications)

  # collect each side's distinct labels in first-seen order.
  seen_applicants: set[Applicant] = set()
  seen_jobs: set[Job] = set()
  applicants: list[Applicant] = []
  jobs: list[Job] = []

  for applicant, job in edges:
    if applicant not in seen_applicants:
      seen_applicants.add(applicant)
      applicants.append(applicant)
    if job not in seen_jobs:
      seen_jobs.add(job)
      jobs.append(job)

  network: FlowNetwork[_Label] = FlowNetwork()
  middle_edges: list[tuple[Applicant, Job, FlowEdge[_Label]]] = []

  # unit edges: source -> applicant, job -> sink, applicant -> job per pair.
  for applicant in applicants:
    network.add_edge(_SOURCE, ("L", applicant), 1.0)
  for job in jobs:
    network.add_edge(("R", job), _SINK, 1.0)

  for applicant, job in edges:
    forward: FlowEdge[_Label] = network.add_edge(
      ("L", applicant), ("R", job), 1.0
    )
    middle_edges.append((applicant, job, forward))

  if applicants and jobs:
    edmonds_karp(network, _SOURCE, _SINK)

  # a saturated middle edge (flow 1) is a matched applicant-job pair.
  matching: dict[Applicant, Job] = {}
  for applicant, job, edge in middle_edges:
    if edge.flow > 0.5 and applicant not in matching:
      matching[applicant] = job
  return 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^{\prime }$ with an edge $s^{\prime }\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 $\left\{u,v\right\}$ 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. $\text{Edmonds-Karp}$ is immune; its $O(m^{2}n)$ bound never mentions capacities.
• Pseudo-polynomial blowup. $O(m\left|f^{\ast }\right|)$ 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: $\text{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 specialized bounds are far better than the generic ones.

Faster max-flow

$\text{Edmonds-Karp}$ is the version to understand, but it is nowhere near the fastest known. Its $O(V{E}^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.³ 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, which is the bound the Hopcroft-Karp matching algorithm realizes directly.

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.⁴ 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.⁵ 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.⁶ 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 $\text{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 $\left|f\right|=\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 $\left|f\right|+k$.
• $\text{Ford-Fulkerson}$ augments until $G_f$ has no $s$–$t$ path; with integer capacities it runs in $O(m\left|f^{\ast }\right|)=O(m^{2}C)$ (pseudo-polynomial), and on irrational capacities it may fail to terminate at all.
• $\text{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 $\leftrightarrow$ $G_f$ has no augmenting path $\leftrightarrow$$\left|f\right|=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.