Network Flow

A flow network models a resource moving through capacity-limited directed connections: packets through links, goods through routes, water through pipes, assignments through eligibility edges, or people through an evacuation plan. The central problem is to send as much as possible from a source to a sink without exceeding capacities or creating resources at intermediate vertices.

The decisive idea is the residual graph. A tentative decision is not permanent: later paths may cancel and reroute earlier flow through reverse residual edges. This ability turns a sequence of locally chosen augmenting paths into a globally optimal solution.

Flow Networks

A flow network is a directed graph G=(V,E) with:

• a source s;
• a distinct sink t;
• a nonnegative capacity c(u,v) for every directed edge;
• normally, no incoming edges to s and no outgoing edges from t in the simplest model, though algorithms do not fundamentally require those restrictions.

A flow f(u,v) assigns a quantity to edges. Its value is net flow leaving the source:

With standard source assumptions this is simply total outgoing source flow. Conservation makes the same quantity equal net flow entering the sink.

Capacities may be integers or real numbers. The classic Ford–Fulkerson termination claim depends on integer capacities; representation and numeric policy must be part of the contract.

Flow Constraints

A feasible flow satisfies two conditions.

Capacity Constraints

For every edge:

Flow cannot be negative on an original directed edge and cannot exceed its capacity.

Flow Conservation

For every internal vertex u other than s and t:

Whatever enters an internal vertex must leave it. This is an invariant of augmentation: an augmenting path adds the same amount to one incoming and one outgoing path edge at each internal vertex.

Multiple Sources

Several sources can be replaced by a super-source with edges into the original sources. Several sinks can be replaced by a super-sink. Choose capacities large enough not to constrain the intended model, preferably the sum of relevant finite capacities rather than an overflow-prone “infinity.”

Residual Graphs

For current flow f, the residual capacity expresses how much the solution can change.

• Forward residual capacity: c_f(u,v)=c(u,v)-f(u,v).
• Reverse residual capacity: c_f(v,u)=f(u,v).

If 3 units flow on an edge of capacity 7, the residual graph permits:

4 more units forward
3 units backward (canceling previously sent flow)

Reverse edges do not mean the physical network suddenly gained a pipe in the opposite direction. They encode the legal operation “undo some earlier decision.”

Rerouting Example

Suppose an early path sends flow through A->B. A later opportunity needs A to route elsewhere while another vertex supplies B. A residual path can traverse B->A, subtracting flow from A->B, then redirect the released capacity. An algorithm that considers only unused forward capacity can become trapped below the optimum.

For capacities S->A=1, S->B=1, A->B=1, A->T=1, and B->T=1, first sending one unit along S-A-B-T leaves reverse residual arc B->A=1. The next residual path S-B-A-T uses that arc to cancel the earlier A->B unit. The resulting value is two, represented by direct paths S-A-T and S-B-T. Without reverse arcs, the first choice would trap the method at value one.

When original edges exist in both directions, residual bookkeeping must combine original unused capacity with cancelable opposite flow carefully. A residual-capacity matrix works for maximum-flow value, but reconstructing individual antiparallel edge flows may require explicit paired edge records.

Augmenting Paths

An augmenting path is an s-to-t path in the residual graph using only positive-capacity edges. Its bottleneck is:

Augment by Delta:

for each residual edge u->v on the path:
    residual[u][v] -= Delta
    residual[v][u] += Delta

At least one residual arc on the path reaches zero capacity. The opposite residual capacity grows by exactly the same amount.

Feasibility Preservation

• Delta does not exceed any residual capacity, so no capacity becomes negative.
• Forward augmentation cannot exceed original capacity.
• Reverse augmentation cancels at most the flow already present.
• Every internal path vertex gains Delta on one incident path edge and loses Delta on another, preserving conservation.
• Source net outflow and sink net inflow both increase by Delta.

Thus every augmentation transforms one feasible flow into a larger feasible flow.

Flow Decomposition

Every feasible flow can be explained as a collection of weighted source-to-sink paths plus weighted directed cycles. While positive net flow remains at s, start there, follow edges carrying positive flow, and extract an s-to-t path. Conservation prevents the walk from becoming stuck at an internal vertex; cycles encountered along the walk can be removed and recorded before continuing. After the source value has been exhausted, start from any remaining positive-flow edge. Conservation then forces the walk eventually to repeat a vertex, producing a directed cycle. Subtract the minimum edge flow from each extracted path or cycle. Every subtraction makes at least one positive-flow edge zero, so at most E components are needed altogether.

Cycle components contribute nothing to the net flow value. Removing them leaves a feasible flow of the same value, which is why a maximum flow always has a path-only representation even if an algorithm’s intermediate residual decisions create circulation. For unit integral capacities, the decomposition gives edge-disjoint s-t paths directly: every path component carries one unit and no original edge can appear in two of them.

The theorem separates two views of the same result. Edge flows are convenient for checking capacity and conservation; path decomposition is convenient for explaining routes, assignments, or disjoint paths to a caller.

Ford-Fulkerson

Ford–Fulkerson is a method rather than one fully specified traversal algorithm:

initialize zero flow and residual capacities equal to capacities
while any residual augmenting path P exists:
    Delta = bottleneck capacity on P
    augment Delta along P
return flow

With nonnegative integer capacities, every augmentation increases flow value by at least one, so the method terminates after at most |f*| augmentations, where |f*| is the maximum-flow value. If path search costs O(E), the bound is O(E|f*|).

This is pseudo-polynomial: |f*| is a numeric value, potentially exponential in the number of bits used to encode capacities. With irrational capacities and unfortunate path choices, generic Ford–Fulkerson may fail to terminate; with real floating-point arithmetic, tiny residual errors need explicit tolerance policy.

Path Choice Matters

Two path orders can perform dramatically different numbers of augmentations. Depth-first search is simple but gives only the value-dependent bound. Edmonds–Karp fixes path choice to shortest residual paths in edge count and obtains a polynomial bound independent of capacity magnitudes.

Edmonds-Karp

Edmonds–Karp chooses each augmenting path with BFS in the residual graph.

while BFS finds t from s using positive residual edges:
    recover path with parent[]
    find its minimum residual capacity
    update forward and reverse residual capacities

BFS Augmentations

Use capacities:

S->A 10     S->B 5
A->B 15     A->T 10
B->T 10

Initially BFS finds a two-edge route before the three-edge alternative:

No positive residual edge now leaves S, so a third BFS cannot reach T. The residual reachable set is {S}. Original edges crossing from {S} to {A,B,T} have total capacity 10+5=15, exactly matching the flow. The augmentations construct a feasible lower bound of 15, while the cut supplies an upper bound of 15; equality proves optimality before any implementation detail is considered.

Edmonds–Karp in C

The matrix implementation is suitable for moderate dense networks. It uses int64_t capacities, supports zero capacity, and preflights both total-flow accumulation and reverse-residual additions before mutating an augmenting path.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define FLOW_MAX_VERTICES 128

typedef enum {
    FLOW_OK,
    FLOW_INVALID,
    FLOW_OVERFLOW
} FlowStatus;

static bool residual_bfs(size_t n,
                         int64_t residual[FLOW_MAX_VERTICES][FLOW_MAX_VERTICES],
                         size_t source, size_t sink, int parent[]) {
    bool seen[FLOW_MAX_VERTICES] = {false};
    size_t queue[FLOW_MAX_VERTICES];
    size_t front = 0;
    size_t back = 0;

    parent[source] = -1;
    seen[source] = true;
    queue[back++] = source;

    while (front < back) {
        size_t u = queue[front++];
        for (size_t v = 0; v < n; ++v) {
            if (!seen[v] && residual[u][v] > 0) {
                seen[v] = true;
                parent[v] = (int)u;
                if (v == sink) {
                    return true;
                }
                queue[back++] = v;
            }
        }
    }
    return false;
}

FlowStatus edmonds_karp(size_t n,
                        const int64_t capacity[FLOW_MAX_VERTICES][FLOW_MAX_VERTICES],
                        size_t source, size_t sink, int64_t *maximum,
                        int64_t residual[FLOW_MAX_VERTICES][FLOW_MAX_VERTICES]) {
    if (n == 0U || n > FLOW_MAX_VERTICES || source >= n || sink >= n ||
        source == sink || maximum == NULL || capacity == NULL || residual == NULL) {
        return FLOW_INVALID;
    }

    for (size_t u = 0; u < n; ++u) {
        for (size_t v = 0; v < n; ++v) {
            if (capacity[u][v] < 0) {
                return FLOW_INVALID;
            }
        }
    }
    for (size_t u = 0; u < n; ++u) {
        for (size_t v = 0; v < n; ++v) {
            residual[u][v] = capacity[u][v];
        }
    }

    int64_t total = 0;
    int parent[FLOW_MAX_VERTICES];
    while (residual_bfs(n, residual, source, sink, parent)) {
        int64_t bottleneck = INT64_MAX;
        for (size_t v = sink; v != source; v = (size_t)parent[v]) {
            size_t u = (size_t)parent[v];
            if (residual[u][v] < bottleneck) {
                bottleneck = residual[u][v];
            }
        }

        if (total > INT64_MAX - bottleneck) {
            return FLOW_OVERFLOW;
        }
        for (size_t v = sink; v != source; v = (size_t) parent[v]) {
            size_t u = (size_t) parent[v];
            if (residual[v][u] > INT64_MAX - bottleneck) {
                return FLOW_OVERFLOW;
            }
        }

        total += bottleneck;
        for (size_t v = sink; v != source; v = (size_t)parent[v]) {
            size_t u = (size_t)parent[v];
            residual[u][v] -= bottleneck;
            residual[v][u] += bottleneck;
        }
    }

    *maximum = total;
    return FLOW_OK;
}

For a network without antiparallel original edges, original flow on (u,v) is capacity[u][v]-residual[u][v]. With antiparallel edges, use explicit residual edge pairs if individual original-edge flows must be recovered unambiguously.

The matrix BFS scans Theta(V^2) entries. Edmonds–Karp performs O(VE) augmentations, so this matrix implementation takes O(V^3 E) time. A paired-edge adjacency-list implementation scans O(E) arcs per BFS and yields the standard O(VE^2) bound.

On FLOW_OVERFLOW, residual describes the state after the last fully completed augmentation; the failing path is not partially applied, and *maximum is left unchanged. Callers that need failure to preserve the original residual matrix must run into a temporary buffer and copy it back only on FLOW_OK.

Edmonds-Karp Complexity

The key theorem is that BFS distance from s to every residual vertex never decreases across augmentations. Moreover, whenever an edge becomes critical—saturated on a shortest augmenting path—before it can become critical again in the same direction, its tail’s BFS distance must increase by at least two. Each directed edge is critical at most O(V) times; therefore there are O(VE) augmentations. With adjacency lists, each BFS and path update is O(E), giving:

This bound is independent of the maximum-flow numeric value and applies to integer or rational capacities represented exactly.

Minimum Cuts

An s-t cut partitions vertices into S and T=V-S, with s in S and t in T. Its capacity is the sum of capacities of original edges directed from S to T:

Edges from T back to S do not add to cut capacity.

Every feasible flow satisfies:

for every cut. Intuitively, all net source-to-sink flow must cross from S to T, and those forward edges have limited total capacity. Thus any cut provides an upper bound on maximum flow.

Flow Duality

The max-flow min-cut theorem states:

The maximum value of an s-t flow equals the minimum capacity of an s-t cut.

When no augmenting path remains, let S be the vertices reachable from s in the residual graph; t is outside S.

• Every original edge from S to T has zero forward residual capacity, so it is saturated.
• Every original edge from T to S carries zero flow; otherwise its reverse residual edge would let the endpoint in T become reachable.
• Therefore net flow across the cut equals exactly its capacity.

We already know every flow value is at most every cut capacity. Finding a flow and cut with equal value proves both are optimal. This is a certificate of optimality, not merely a termination condition.

Extracting the Minimum Cut

After Edmonds–Karp terminates, run one more residual BFS or DFS from s. Reachable vertices form S; all others form T. Report original edges from S to T with positive capacity. Their capacities sum to the maximum-flow value, subject to exact arithmetic.

Bipartite Matching

A bipartite graph has left vertices L, right vertices R, and edges only between the two sets. A matching selects edges sharing no endpoint. To find a maximum-cardinality matching, build a flow network:

1. add source s;
2. add capacity-one edges s -> u for every u in L;
3. orient every bipartite edge u -> v from L to R, capacity one;
4. add capacity-one edges v -> t for every v in R.

Every integral unit of flow follows s-u-v-t and corresponds to matching edge (u,v). Capacity one at vertices ensures no endpoint is used twice.

Integrality

With integer capacities, augmenting-path algorithms maintain integer flow. Therefore the maximum flow in this network is integral and maps directly to a matching; no fractional assignment appears.

Matching Trace

Let applicants A,B,C be eligible for jobs:

A: X, Y
B: X
C: Y, Z

One maximum matching is A-Y, B-X, C-Z, of size three. A poor first choice A-X may temporarily block B, but a reverse residual path can reassign A to Y and release X for B. Residual cancellation is exactly augmenting-path reassignment in matching language.

Generic Edmonds–Karp solves the reduction. Hopcroft–Karp exploits bipartite structure to run in O(E sqrt(V)), finding a maximal set of vertex-disjoint shortest augmenting paths per phase.

For weighted assignments, min-cost maximum flow or the Hungarian algorithm is appropriate; ordinary max flow optimizes quantity, not preference cost.

Capacity Scaling

Capacity scaling reduces the number of unproductive small augmentations for integer capacities.

1. Let Delta be the largest power of two not exceeding the largest capacity.
2. Search only residual edges with capacity at least Delta.
3. Augment while such paths exist.
4. Halve Delta and repeat until Delta=1.

On the earlier network, the largest capacity is 15, so the thresholds are 8,4,2,1:

The amount need not equal Delta; it is the path’s actual bottleneck and is guaranteed to be at least Delta.

The augmentation bound follows from a cut argument. At the end of the previous 2Delta scale, let S be vertices reachable from the source using residual arcs of capacity at least 2Delta. The sink is outside S, and every residual arc crossing this cut has capacity less than 2Delta. The same statement holds before the first scale because the chosen starting Delta makes every original capacity less than 2Delta. An original graph with E edges has at most 2E directed residual arcs, so this cut has residual capacity less than 4E Delta. The max-flow min-cut bound says less than 4E Delta additional flow remains possible. Every augmentation during the Delta scale sends at least Delta, so fewer than 4E, and therefore O(E), augmentations occur at that scale.

There are floor(log2 U)+1 scales. If a path search and update costs O(E), the resulting time is O(E^2 log U), where U is the largest integer capacity. The logarithm depends on capacity bit length, improving the pseudo-polynomial O(E|f*|) behavior. When all capacities are zero there is no positive starting scale and the answer is immediately zero.

Scaling is one strategy family. Other max-flow algorithms use level graphs, blocking flows, dynamic trees, and push-relabel operations to improve theoretical or practical performance.

Dinic Algorithm

Dinic groups many augmentations into one phase.

1. BFS in the residual graph assigns level[v], the shortest residual edge count from s.
2. Keep only admissible arcs satisfying level[v]=level[u]+1; these form an acyclic level graph.
3. Send a blocking flow through that graph: after it finishes, every s-to-t path in the level graph contains a saturated arc.
4. Rebuild levels and repeat.

DFS commonly sends the blocking flow. A current-arc index remembers which outgoing arcs have already failed, preventing every DFS call from rescanning them. Reverse residual arcs are still updated, but an arc that goes to the same or an earlier level is not admissible during the current phase.

After a blocking flow, no residual path of the old shortest length remains. Reverse arcs created by augmentation go backward one level, so they cannot recreate an admissible path of that length. The next BFS therefore either finds the sink farther away or proves it unreachable. Since a simple path has fewer than V edges, there are fewer than V successful phases.

With adjacency lists and current-arc optimization, a blocking-flow phase costs O(VE) in the general analysis, giving O(V^2E) total. Stronger bounds hold for unit networks, including matching reductions. Dinic is usually a better competition implementation than Edmonds–Karp when input sizes are large, but its residual edge pairing and current-arc invariants demand more careful code.

Flow Demands

Some networks require lower as well as upper bounds: edge (u,v) must carry l(u,v) <= f(u,v) <= c(u,v). Sending the lower bounds first can violate conservation. Record each vertex’s balance after these mandatory shipments:

Replace every original capacity by c(u,v)-l(u,v). Add a super-source S* and super-sink T*:

• if b(v)>0, add S*->v with capacity b(v) because v received excess mandatory inflow that must be routed onward;
• if b(v)<0, add v->T* with capacity -b(v) because v sent excess mandatory outflow that must be replenished.

Using the opposite balance convention reverses those two edge directions; the equations, not a memorized diagram, should determine the construction. A feasible circulation exists exactly when a maximum flow from S* to T* saturates every edge leaving S*. Recover original flow by adding each lower bound back.

For an s-t flow problem with demands, add a sufficiently large edge t->s before this feasibility transformation. Its recovered flow represents the initial feasible s-t value; after removing the auxiliary vertices and edge, residual augmentation from s to t can maximize beyond it. The chosen “large” capacity must be a checked finite bound, such as the sum of source outgoing upper capacities, rather than an unsafe numeric sentinel.

Flow Costs

All require O(V+E) residual state with adjacency lists. A matrix requires Theta(V^2) storage and turns a BFS scan into Theta(V^2).

Flow Applications

• maximum bipartite matching and assignment feasibility;
• edge-disjoint paths by assigning unit edge capacities;
• vertex-disjoint paths by splitting each vertex into in/out copies connected by capacity one;
• project selection and maximum-weight closure through a min-cut reduction;
• image segmentation with source/sink label costs and neighborhood penalties;
• circulation with demands after adding super-source and super-sink transformations;
• transportation, bandwidth allocation, and evacuation under a static divisible-flow model.

The model assumes a conserved divisible quantity and usually ignores travel time, queues, uncertainty, and simultaneous multi-commodity competition. Time-expanded networks, min-cost flow, or multi-commodity formulations handle different questions.

Flow Pitfalls

• Omitting reverse residual edges, preventing rerouting.
• Searching original edges rather than positive residual edges.
• Computing a bottleneck from original capacities instead of residual capacities.
• Updating the forward residual edge but not the reverse one.
• Adding capacities from both directions when computing an S-to-T cut.
• Using negative capacities or source == sink without a defined contract.
• Overflowing total flow, residual sums, or super-source capacities.
• Assuming generic Ford–Fulkerson has a polynomial bound.
• Recovering original flows incorrectly when antiparallel edges share a residual matrix.
• Reducing weighted matching to ordinary max flow and losing the weight objective.
• Reporting a maximum-flow value without preserving enough state to return edge flows or a min-cut certificate.

Choosing a Flow Method

• Need a clear, dependable general implementation on moderate graphs: Edmonds–Karp.
• Capacities are small integers and instances are simple: Ford–Fulkerson may suffice.
• Capacities are large integers and path augmentation is retained: capacity scaling improves value dependence.
• Problem is unweighted bipartite matching at scale: Hopcroft–Karp.
• Need costs as well as maximum quantity: min-cost maximum flow.
• Need very large generic maximum flow: consider Dinic or push-relabel rather than treating Edmonds–Karp as the final word.

Always return or retain a residual graph. It supplies rerouting during computation and the minimum-cut certificate afterward.

Flow Review

• Feasible flow obeys edge capacities and conservation at internal vertices.
• Residual forward edges represent unused capacity; reverse edges represent cancelable prior flow.
• Augmenting by a path bottleneck preserves feasibility and increases flow value.
• Ford–Fulkerson is a general augmenting-path method with a pseudo-polynomial integer-capacity bound.
• Edmonds–Karp uses BFS and runs in O(VE^2) with adjacency lists.
• When no augmenting path remains, residual reachability exposes a cut whose capacity equals flow value, proving max-flow min-cut duality.
• Unit-capacity flow reduces bipartite matching to maximum flow; integrality maps units back to matching edges.
• Capacity scaling, Hopcroft–Karp, Dinic, min-cost flow, and push-relabel refine the method for particular needs.
• Flow decomposition turns edge assignments into weighted paths and removable cycles.
• Capacity scaling has O(E) augmentations per scale by a residual-cut bound; Dinic blocks all shortest paths in each phase.
• Lower bounds and conservation demands reduce to saturating super-source edges in an auxiliary circulation network.

Flow Problems

Flow Vocabulary

1. State capacity constraints, conservation, and flow value.
2. Explain the semantic meaning of a reverse residual edge.
3. Define an augmenting path and its bottleneck.
4. Why does equal flow value and cut capacity certify optimality?

Residual Traces

5. Trace Ford–Fulkerson on the reverse-edge example, showing every residual change.
6. Run Edmonds–Karp on capacities S->A=7, S->B=4, A->B=3, A->T=5, B->T=6. List BFS parents, bottlenecks, and total flow.
7. After exercise 6, extract the residual reachable set and minimum-cut edges.

Cut Proofs

8. Prove augmentation preserves conservation at every internal path vertex.
9. Prove that every feasible flow value is bounded by every cut capacity.
10. Prove the matching-flow correspondence in both directions.
11. Explain why the reachable residual set at termination saturates all forward cut edges and carries zero flow on backward cut edges.

Residual Faults

12. Construct a network where an implementation without reverse residual edges returns a suboptimal value.
13. Give a network with antiparallel original edges and explain why capacity[u][v]-residual[u][v] alone may not recover both original flows.
14. Show how using int can overflow when summing several legal capacities even if each capacity fits individually.

Flow Programming

15. Convert the matrix Edmonds–Karp implementation to paired adjacency-list residual edges.
16. Extend it to return original edge flows and the minimum-cut partition.
17. Implement the bipartite reduction and translate unit-flow edges back into matched pairs.
18. Implement capacity scaling and compare augmentations with DFS Ford–Fulkerson and Edmonds–Karp.

Flow Reductions

19. Reduce maximum edge-disjoint s-t paths to flow and prove the returned value counts paths.
20. Reduce maximum vertex-disjoint paths by vertex splitting, handling source and sink carefully.
21. Model a project-selection problem where profitable projects require prerequisite projects as a min-cut instance.

Flow Extensions

22. Derive Dinic’s level-graph idea from Edmonds–Karp: explain why finding a blocking flow can eliminate an entire shortest-path layer length in one phase.
23. Extend the model to edges with lower bounds and vertex demands. Transform feasibility into a circulation problem with a super-source and super-sink.