Network Flow, Matching and Graph Optimization

Introduction and Context

Many planning problems ask how a scarce, divisible resource should move through a network. A logistics firm routes goods through warehouses, a telecommunications operator carries packets through links, and a hospital assigns staff to shifts. These problems share a mathematical structure: resources enter a network, traverse constrained arcs, and eventually reach destinations. Network-flow theory provides algorithms with strong optimality guarantees for such decisions.

The central ideas are maximum flow, minimum cut, circulation, bipartite matching, and assignment. Their importance extends beyond graph theory because many scheduling, transportation, allocation, and connectivity problems can be transformed into one of these models. This chapter develops the theory, algorithms, modelling assumptions, implementation considerations, and managerial interpretation of these transformations.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Formulate directed capacitated networks and interpret feasible flows.
2. Compute maximum flows using augmenting-path algorithms.
3. Explain and apply the max-flow/min-cut theorem.
4. Model lower bounds, supplies, demands, and costs through circulation.
5. Reduce bipartite matching and assignment problems to network optimization.
6. Select algorithms according to graph size, capacities, costs, and application requirements.
7. Interpret solutions, bottlenecks, sensitivity, and limitations in operational settings.

1. Network-Flow Foundations

A directed network is a graph G=(V,E) with a source s, a sink t, and a nonnegative capacity c(u,v) on each directed edge. The capacity is the maximum amount that may traverse the edge. Capacities may represent tonnes per hour, packets per second, workers, or any other divisible quantity.

A flow f(u,v) satisfies two conditions:

• Capacity constraint: 0≤f(u,v)≤c(u,v).
• Conservation: for every vertex other than s and t, inflow equals outflow.

The value of a flow is the net amount leaving the source:

Here, |f| is measured in the same units as capacity. The standard model assumes directed arcs, nonnegative capacities, divisible flow, and no conservation requirement at the source and sink. If the application requires indivisible units, ordinary maximum flow may not by itself describe the problem; integrality results are relevant only under suitable integer data and network structure.

Residual Networks

Given a flow, the residual capacity of an arc from u to v is the amount of additional flow that can be sent in that direction. The residual network contains:

• a forward arc with residual capacity c(u,v)−f(u,v), and
• a reverse arc with residual capacity f(u,v), allowing an algorithm to cancel previously chosen flow.

Reverse arcs are essential. An early routing choice may be locally reasonable but globally poor; a later augmenting path can undo part of it.

2. Maximum Flow and Minimum Cut

A maximum flow is a feasible flow with greatest value. A cut is a partition (S,T) of the vertices such that s∈S and t∈T. Its capacity is the sum of capacities of arcs directed from S to T:

Every feasible flow satisfies |f|≤c(S,T) for every s−t cut, because all source-to-sink flow must cross the cut. The max-flow/min-cut theorem strengthens this observation:

The value of a maximum flow equals the capacity of a minimum s−t cut.

This theorem has both algorithmic and managerial meaning. A flow is certified as optimal when a cut of equal capacity is identified. The cut also reveals a bottleneck: increasing capacities outside the minimum cut cannot increase throughput unless another structural limitation becomes active.

Augmenting-Path Method

The generic method begins with zero flow and repeatedly finds an s−t path in the residual network. If the path is P, its bottleneck residual capacity is:

The algorithm adds Δ along forward arcs and subtracts it along reverse arcs. It stops when no residual path from s to t exists. The vertices reachable from s in the final residual network form a minimum-cut side S.

Ford–Fulkerson and Edmonds–Karp

Ford–Fulkerson is a framework whose running time depends on the path-selection rule. With integer capacities and arbitrary augmenting paths, it terminates after at most |f^*| unit augmentations in the worst case, where f^* is the optimal value; this can be poor when capacities are large.

Edmonds–Karp always chooses a shortest residual path in number of edges using breadth-first search. Its worst-case time is:

where V=|V| and E=|E|. This bound is polynomial and independent of the magnitude of capacities. In practice, Dinic’s blocking-flow algorithm, push–relabel methods, or specialized capacity-scaling algorithms are often faster on large instances.

Worked Example: A Small Maximum Flow

Consider arcs with capacities: s→a=10, s→b=8, a→b=2, a→t=7, b→t=9.

Choose the path s→a→t. Its bottleneck is min(10,7)=7, so send 7. Next choose s→b→t, whose bottleneck is min(8,9)=8, so send 8. The current flow is 15. The remaining source capacity is 3 on s→a, but a→t is saturated; the arc a→b has capacity 2 and b→t has only 1 unit of residual capacity. Thus an additional 1 unit can be sent through s→a→b→t, producing flow 16.

The cut S={s,a}, T={b,t} has capacity c(s,b)+c(a,b)+c(a,t)=8+2+7=17, so it does not yet certify 16. Instead, after the third augmentation, the cut S={s,a,b}, T={t} has capacity 7+9=16, equal to the flow. Therefore the maximum flow is 16.

3. Integrality and Modelling Extensions

The integral-flow theorem states that if all capacities are integers, a maximum-flow algorithm can produce an integral maximum flow. This is especially important for assigning discrete workers, vehicles, or units. It does not mean that every optimization model has an integral solution; the property follows from the network matrix and the particular constraints of standard flow models.

Multiple Sources and Sinks

A problem with several sources can be converted to a single-source problem by introducing a super-source and arcs to each original source. Their capacities represent available supply. Similarly, a super-sink can connect from each original destination with capacity equal to its demand or receiving limit. The transformation is valid when these artificial arcs accurately represent the application’s constraints.

Vertex Capacities

If a vertex has capacity b(v), split it into v_in and v_out and add an arc v_in→v_out with capacity b(v). Incoming arcs connect to v_in and outgoing arcs leave v_out. This converts a vertex restriction into an edge restriction.

4. Circulation with Demands, Lower Bounds and Costs

Maximum flow is not sufficient when internal vertices have specified supplies or demands, or when every arc must carry a minimum amount. A circulation is a flow in which conservation is enforced at every vertex. For an arc (u,v), a lower and upper bound may be specified:

Here ℓ is the minimum required flow and u is the maximum. A feasible circulation must satisfy conservation at every vertex while respecting all bounds.

Reduction of Lower-Bound Circulation

Set the initial flow on each arc to its lower bound. This creates an imbalance because sending ℓ(u,v) units gives vertex v inflow and vertex u outflow. Define the demand balance:

Add a super-source S and super-sink T. For every vertex with b(v)>0, add S→v with capacity b(v). For every vertex with b(v)<0, add v→T with capacity −b(v). Original arcs receive residual capacity u−ℓ. A feasible circulation exists exactly when a maximum flow saturates every arc leaving S (equivalently, all arcs entering T).

For minimum-cost circulation, each arc additionally has cost w(u,v) per unit. The objective is:

subject to capacity bounds and conservation. Successive shortest augmenting path, cycle-canceling, cost-scaling, and linear-programming methods are common solution approaches. Negative-cost arcs require careful treatment; shortest-path computations may use potentials or Bellman–Ford-style initialization rather than an unmodified Dijkstra algorithm.

5. Bipartite Matching

A bipartite graph has vertex sets L and R with edges only between the two sets. A matching is a set of edges sharing no endpoint. In workforce planning, L may represent employees and R shifts; an edge indicates eligibility.

A maximum-cardinality matching contains as many edges as possible. It can be reduced to maximum flow by adding a source s, arcs s→ℓ of capacity 1 for every ℓ∈L, arcs ℓ→r of capacity 1 for every eligible pair, and arcs r→t of capacity 1 for every r∈R. Integral maximum flow corresponds directly to a matching.

A matching is maximum if no augmenting path exists in the associated alternating graph. An alternating path switches between unmatched and matched edges. The classic augmenting-path algorithm repeatedly finds such paths and reverses their edge status. Its simple implementation is effective for moderate graphs; Hopcroft–Karp improves the worst-case bound to:

for unweighted bipartite matching.

Hall’s Theorem

A bipartite graph has a matching that covers every vertex in L if and only if, for every subset X⊆L, the neighborhood N(X) satisfies:

The theorem explains infeasibility: a group of workers collectively eligible for too few positions creates a structural shortage. In applications, a minimum cut can identify such a constrained group.

6. Assignment and Weighted Matching

The assignment problem matches each agent to one position, usually with a cost or benefit. Let c_ij be the cost of assigning agent i to job j. For n agents and n jobs, the binary formulation is:

subject to

The variables x_ij equal 1 when agent i receives job j. The first constraints assign every agent once; the second fill every job once. For unequal set sizes or optional assignments, dummy vertices and suitable zero or penalty costs can balance the model.

The assignment problem is a minimum-cost flow problem: send one unit from a source to each agent, one unit across an eligible assignment edge, and one unit from each job to the sink. The Hungarian algorithm solves the square dense assignment problem in O(n³). Its row and column reductions preserve the set of optimal assignments while creating zero-cost opportunities.

Illustrative Assignment Calculation

Suppose three analysts must be assigned to three projects with cost matrix:

The assignment A1→P1, A2→P3, A3→P2 has total cost 4+3+1=8. Alternative A1→P2, A2→P1, A3→P3 costs 2+6+6=14, while A1→P3, A2→P2, A3→P1 costs 7+5+8=20. Checking the remaining permutations gives costs 15, 21, and 21; hence cost 8 is optimal. If the entries represent time rather than monetary cost, the unit is analyst-hours or another explicitly defined measure, and interpretation must not silently mix units.

7. A Detailed Applied Case: Regional Emergency-Supply Distribution

Background

This illustrative case concerns a public agency distributing emergency water from two depots to three shelters through a constrained road network. Depot capacities and road capacities are measured in thousand litres per hour. The agency wants to maximize deliverable water during a critical operating window.

Problem

Let the source connect to depots D1 and D2 with capacities 12 and 10. Roads are D1→H1 with capacity 7, D1→H2 with capacity 6, D2→H2 with capacity 5, and D2→H3 with capacity 8. Shelter links to the super-sink have capacities H1→t = 7, H2→t = 8, and H3→t = 6.

Analysis and Approach

Create a super-source representing available water and a super-sink representing shelter demand. A maximum-flow algorithm sends water through residual paths. One feasible routing is 7 through D1→H1, 5 through D1→H2, 3 through D2→H2, and 6 through D2→H3, giving 21. The shelter capacities total 21, so no solution can exceed 21. Since the routing achieves 21, it is optimal.

The minimum cut separating all shelters from the sink has capacity 7+8+6=21. It is therefore a certificate of optimality. Operationally, additional depot supply cannot increase throughput unless shelter receiving capacity or another cut is expanded.

Outcome and Learning Points

The result identifies both a delivery plan and a capacity diagnosis. The agency should prioritize improvements at shelter intake if demand remains unmet, rather than merely increasing depot stock. If road failures are possible, the deterministic solution should be supplemented by scenario analysis, robust optimization, or stochastic network models. If water must be allocated fairly, maximizing total flow alone may be inadequate; lower bounds, priority weights, or lexicographic objectives may be required.

8. Algorithm Selection and Implementation

A practical implementation should use adjacency lists containing both forward and reverse residual edges. Each residual edge stores its endpoint, residual capacity, and an index identifying its reverse edge. This representation makes augmentation and cancellation efficient.

Important implementation practices include validating nonnegative capacities, preserving reverse arcs, using sufficiently wide numeric types, checking conservation after solution, and reporting both the objective value and a certificate such as a cut or reduced-cost condition. Parallel edges should be supported rather than accidentally merged. Disconnected vertices, zero-capacity arcs, and infeasible demands should be tested explicitly.

9. Complexity, Sensitivity and Limitations

Complexity depends on the algorithm and graph representation. A theoretical polynomial bound does not guarantee low operational latency; memory locality, capacity ranges, graph density, and repeated reoptimization matter. When a network changes slightly, warm starts or incremental algorithms may outperform solving from scratch.

A minimum cut provides a first sensitivity diagnosis, but capacity changes can alter the identity of the minimum cut. Therefore, claims about the value of expanding an arc should be tested by re-solving or by parametric analysis. In cost-flow models, dual variables and reduced costs provide more refined marginal information, subject to degeneracy and model assumptions.

Network models also simplify reality. They may omit travel-time uncertainty, congestion interaction, indivisibility, preferences, labor regulations, or nonlinear costs. A maximum-flow solution can be operationally unfair if it concentrates resources on one region. A matching model can encode discriminatory historical eligibility rules. Mathematical optimality is conditional on the objective, constraints, and data quality.

10. Governance, Ethics and Contemporary Developments

Network optimization increasingly supports automated decisions about staff, transport, communications, and public services. Governance requires documenting data sources, eligibility rules, objective weights, and tie-breaking procedures. Decision-makers should audit whether protected groups receive systematically worse outcomes, whether emergency priorities are represented, and whether a human can review exceptional assignments.

Modern solvers combine network algorithms with mixed-integer programming, robust optimization, and machine-learning forecasts. Forecasts may estimate demand or travel time, while the flow model determines feasible allocation. Forecast error should be stress-tested; AI prediction does not remove the need for capacity constraints, explainability, and accountability. Privacy controls are necessary when worker or patient attributes are used. Reproducible model versions, solver logs, and post-deployment monitoring are best practices.

Best-Practice Checklist

1. Define vertices, arcs, units, and direction explicitly.
2. Distinguish capacity, demand, cost, and priority.
3. Verify conservation and eligibility constraints.
4. Use residual reverse arcs correctly.
5. Report a bottleneck or optimality certificate.
6. Test infeasibility and boundary cases.
7. Examine sensitivity rather than assuming every capacity expansion helps.
8. Validate fairness, legal compliance, uncertainty, and operational feasibility.
9. Preserve audit trails for data, model, parameters, and decisions.

Chapter Summary

Network flow models represent the movement of divisible resources through capacity-constrained directed graphs. Feasible flows obey capacity and conservation constraints, while maximum flow seeks the greatest source-to-sink throughput. Residual networks permit correction of earlier choices, and the max-flow/min-cut theorem supplies both an optimality proof and a bottleneck interpretation.

Circulation extends the framework to lower bounds, supplies, demands, and costs. Bipartite matching is a unit-capacity flow problem, and Hall’s theorem characterizes complete coverage. Weighted assignment is a minimum-cost flow model and can be solved efficiently by the Hungarian algorithm. In practice, algorithm selection depends on graph structure, capacities, costs, and scale. Correct modelling also requires attention to uncertainty, fairness, privacy, legal obligations, and auditability.

Key Terms

Network flow: Movement of a quantity through directed, capacity-constrained arcs.

Capacity: Maximum permitted flow on an arc.

Flow conservation: Equality of inflow and outflow at an internal vertex.

Source: Vertex from which net flow originates.

Sink: Vertex at which net flow terminates.

Residual network: Network describing remaining and reversible flow possibilities.

Augmenting path: Residual source-to-sink path used to increase flow.

Cut: Partition separating source from sink.

Minimum cut: Cut with least total forward capacity.

Max-flow/min-cut theorem: The maximum flow value equals minimum cut capacity.

Circulation: Flow satisfying conservation at every vertex.

Lower bound: Minimum required flow on an arc.

Minimum-cost flow: Feasible flow minimizing total arc cost.

Bipartite graph: Graph whose vertices divide into two independently connected sets.

Matching: Set of edges with no shared endpoints.

Augmenting path in matching: Alternating path that increases matching size.

Assignment problem: One-to-one allocation of agents to positions under costs or benefits.

Hall’s theorem: Condition characterizing whether one bipartition can be fully matched.

Minimum cut certificate: A cut whose capacity proves a flow is optimal.

Integrality property: Existence of an integral optimal flow for integral network capacities.

Review Questions

Short Answer Questions

1. What are the two defining feasibility conditions for a standard flow?
2. Why are reverse arcs included in a residual network?
3. State the max-flow/min-cut theorem.
4. How can a vertex-capacity constraint be represented using edge capacities?
5. What is the role of a dummy job in an unbalanced assignment problem?

Long Answer Questions

1. Explain Ford–Fulkerson and Edmonds–Karp, including their path-selection rules and complexity implications.
2. Derive the lower-bound circulation reduction using a super-source and super-sink.
3. Explain the reduction of bipartite matching to maximum flow and relate it to Hall’s theorem.
4. Formulate the assignment problem as a binary optimization model and as a minimum-cost flow.
5. Discuss how minimum cuts support operational bottleneck analysis and capacity investment decisions.

Analytical / Application Questions

1. A hospital has nurses on the left side of a bipartite graph and shifts on the right. Eligibility edges are given, but one shift must be staffed by at least two nurses. Explain how the basic matching model must be modified.
2. A telecommunications network has a maximum flow of 500 packets per second. A minimum cut consists of three links with capacities 180, 170, and 150 packets per second. Interpret the result and identify what can and cannot be concluded about adding capacity elsewhere.
3. A delivery model maximizes total supply delivered but repeatedly assigns nearly all supply to one district. Propose modelling changes that could improve fairness while preserving feasibility and explain the trade-offs.

Multiple Choice Questions with Answers

Question 1

Which condition must hold at every internal vertex in a standard flow?

A. Inflow equals outflow

B. Inflow is always greater than outflow

C. Outflow equals the vertex capacity

D. Every incident edge is saturated

Correct Answer: A. Inflow equals outflow

Question 2

What does a reverse residual edge represent?

A. A new physical road that must be built

B. The ability to cancel previously sent flow

C. An edge with negative capacity

D. A mandatory return shipment

Correct Answer: B. The ability to cancel previously sent flow

Question 3

If a feasible flow has value 24 and an s–t cut has capacity 24, what follows?

A. The flow is infeasible

B. The cut is not relevant

C. The flow is maximum and the cut is minimum

D. The network must contain a negative cycle

Correct Answer: C. The flow is maximum and the cut is minimum

Question 4

What is the Edmonds–Karp worst-case running time stated in the chapter?

A. O(V)

B. O(E log V)

C. O(VE^2)

D. O(E√V)

Correct Answer: C. O(VE^2)

Question 5

In the standard matching-to-flow reduction, what capacity is placed on an edge from a left vertex to a right vertex?

A. 0

B. 1

C. The number of right vertices

D. Infinity in every implementation

Correct Answer: B. 1

Question 6

According to Hall’s theorem, a matching covering every vertex in L exists when which condition holds for every X⊆L?

A. |N(X)|≤|X|

B. |N(X)|=0

C. |N(X)|≥|X|

D. |N(X)|=|R| regardless of X

Correct Answer: C. |N(X)|≥|X|

Question 7

For the assignment matrix in the chapter, what is the cost of A1→P1, A2→P3, and A3→P2?

A. 6

B. 8

C. 14

D. 20

Correct Answer: B. 8

Question 8

Which algorithm is specifically associated with dense square assignment problems and O(n^3) complexity?

A. Hungarian algorithm

B. Depth-first search

C. Kruskal’s algorithm

D. Binary search

Correct Answer: A. Hungarian algorithm

Question 9

In a lower-bound circulation reduction, what capacity is assigned to an original arc?

A. Lower bound plus upper bound

B. Upper bound minus lower bound

C. Only the lower bound

D. Zero regardless of bounds

Correct Answer: B. Upper bound minus lower bound

Question 10

In the emergency-supply case, why was a flow of 21 optimal?

A. All roads had equal capacity

B. It used no residual network

C. It equaled the total shelter-side cut capacity of 21

D. It exceeded every individual arc capacity

Correct Answer: C. It equaled the total shelter-side cut capacity of 21