Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 38 ยท Network Flows

Max Flow and Min Cut

Compute maximum flow with augmenting paths and Edmonds-Karp, find the minimum cut, understand the max-flow min-cut theorem, and solve flow problems with SciPy and linprog.

How much can you push through a network? Think of water through a pipe system, cars through a road network, or data through a set of links. Each arc has a capacity, and the maximum flow problem asks for the largest total amount that can travel from a source s to a sink t.

This problem has a famous twin, the minimum cut: the cheapest way to separate s from t by cutting arcs. The surprising and beautiful fact is that the two always have the same value.

The LP model

Let x_ij be the flow on arc (i, j) with capacity u_ij, and v the flow value:

TEXT
maximize    v
subject to  out(i) - in(i) = v (i = s), -v (i = t), 0 (otherwise)
            0 <= x_ij <= u_ij

It is a special case of minimum-cost flow: add an arc from t back to s with cost -1 and infinite capacity, and make every other cost 0. Since the constraint matrix is a network matrix, integer capacities give an integer maximum flow.

Augmenting paths

Instead of an LP solver you can use the much faster Ford-Fulkerson idea:

  1. Start with zero flow.
  2. Find a path from s to t with spare capacity in the residual graph.
  3. Push as much as the path's smallest spare capacity (its bottleneck).
  4. Repeat until no path exists.

The residual graph is the key. For every arc (i, j) with flow f and capacity u, it has a forward residual arc with spare capacity u - f and a backward arc (j, i) with capacity f, which lets later paths undo (cancel) earlier flow. Choosing the shortest path (fewest arcs) at each step gives the Edmonds-Karp algorithm, which runs in O(V E^2) regardless of capacities.

flowchart LR
    s((s)) -->|"10"| a((a))
    s -->|"10"| b((b))
    a -->|"2"| b
    a -->|"4"| c((c))
    a -->|"8"| d((d))
    b -->|"9"| d
    d -->|"6"| c
    c -->|"10"| t((t))
    d -->|"10"| t

The network used in the code below (arc labels are capacities).

Python Edmonds-Karp from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed lines show each augmentation. When the loop ends there is no s-t path left in the residual graph.

Cuts and the max-flow min-cut theorem

An s-t cut splits the nodes into a set S containing s and the rest T containing t. Its capacity is the total capacity of arcs going from S to T. Every unit of flow must cross the cut, so the flow value can never exceed the capacity of any cut. The theorem says more:

Max-flow min-cut theorem. The value of a maximum flow equals the capacity of a minimum cut.

Proof sketch: when the algorithm stops, let S be the set of nodes still reachable from s in the residual graph. Every arc from S to T is saturated and every arc from T to S carries zero flow, so the flow across the cut equals its capacity. A flow that matches a cut cannot be improved, so both are optimal. In LP terms the cut problem is the dual of the max-flow LP, and the theorem is strong duality.

Finding the min cut after a run is easy: do one more search from s in the final residual graph.

Python Maximum flow with SciPy and extracting the minimum cut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cut capacity equals the flow value, a numerical check of the theorem.

Variants and uses

  • Multiple sources and sinks: add a super-source and a super-sink with infinite capacity arcs.
  • Node capacities: split a node into in and out parts joined by an arc with the node's capacity.
  • Bipartite matching: match workers to jobs by making a source linked to workers, jobs linked to a sink, all capacities 1. The max flow is the size of a maximum matching.
  • Project selection and image segmentation: profit or similarity problems reduce to a minimum cut.
  • Network reliability and connectivity: the minimum cut counts the arcs whose failure disconnects s from t. With unit capacities the max flow equals the number of arc-disjoint paths (Menger's theorem).
Python Bipartite matching as max flow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four workers and three jobs can match at most three pairs, and the printed list shows one valid choice.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the max-flow min-cut theorem state?

    No flow can exceed any cut's capacity, and at optimality some cut is exactly saturated, so the two values are equal.
  2. 2. What are backward arcs in the residual graph for?

    A backward arc with capacity equal to the current flow lets the algorithm reroute flow, which is needed to reach the optimum.
  3. 3. Why does Edmonds-Karp use breadth-first search?

    Always augmenting along a path with fewest arcs gives O(V E) augmentations, so the total running time is O(V E^2).
  4. 4. How can a maximum bipartite matching be computed with max flow?

    Unit capacities allow each worker and job to be used once; the integral max flow is the matching size.

Summary

  • Max flow finds the largest amount that can be sent from s to t under arc capacities; it is an LP and a network problem.
  • Augmenting paths in the residual graph (Ford-Fulkerson, Edmonds-Karp) solve it without an LP solver.
  • The max-flow min-cut theorem is strong LP duality: the maximum flow equals the minimum cut capacity.
  • The min cut is the set of arcs between nodes reachable from s in the final residual graph and the rest.
  • Matching, disjoint paths, project selection and connectivity are max-flow problems in disguise.

Next: The Transportation Problem