12.23 Complexity Analysis

Problem

Flow algorithms solve the same abstract problem, but their running times differ sharply.

A small network can be solved with almost any implementation. A large scheduling system, matching engine, or transportation model may require careful algorithm selection. The wrong choice can turn a feasible computation into an unusable one.

You need a way to compare flow algorithms by graph size, capacity size, density, and problem structure.

Solution

Analyze a flow problem using four quantities:

V = number of vertices
E = number of edges
F = value of the maximum flow
C = maximum edge capacity

Then choose the algorithm whose bound matches the structure of the graph.

The most common algorithms have these bounds:

Algorithm	Typical Bound	Best Use
Ford-Fulkerson	O(EF)	Small integer-capacity graphs
Edmonds-Karp	O(VE²)	Simple, predictable baseline
Dinic	O(V²E)	General-purpose max flow
Dinic on unit networks	O(E√V) or better	Matching and disjoint paths
Push-relabel	O(V²E) generic	Dense graphs and practical solvers
Min-cost flow with Bellman-Ford	O(FVE)	Small graphs with negative costs
Min-cost flow with potentials	O(FE log V)	Sparse graphs with costs

These are worst-case bounds. Practical performance depends heavily on implementation details, graph shape, and capacity distribution.

Ford-Fulkerson

Ford-Fulkerson repeatedly finds any augmenting path.

If capacities are integers, each augmentation increases the flow by at least one unit.

Each path search costs:

O(E)

Number of augmentations:

O(F)

Total:

O(EF)

This bound depends on the value of the flow, not just the size of the graph.

If capacities are large, this can be poor.

Example:

E = 1,000
F = 1,000,000,000

The bound becomes impractical.

Ford-Fulkerson is acceptable when capacities are small and the implementation must be minimal.

Edmonds-Karp

Edmonds-Karp is Ford-Fulkerson with BFS path selection.

Each BFS costs:

O(E)

The number of augmentations is:

O(VE)

Total:

O(VE²)

The advantage is that the bound no longer depends on the numeric flow value.

This matters when capacities are large.

The disadvantage is that Edmonds-Karp still performs one augmentation per BFS. For large graphs, it is often slower than Dinic.

Dinic

Dinic alternates between BFS level-graph construction and DFS blocking-flow computation.

For general graphs, the usual bound is:

O(V²E)

This is often better than Edmonds-Karp, especially when E is large.

Dinic is a strong default choice because it is:

• fast in practice
• not too difficult to implement
• effective on sparse graphs
• excellent on many unit-capacity problems

Dinic on Unit Networks

When every capacity is:

0 or 1

Dinic becomes faster.

This appears in:

• bipartite matching
• edge-disjoint paths
• vertex-disjoint paths after node splitting
• unit-capacity scheduling models

For many such graphs, the bound improves to roughly:

O(E√V)

This is why Dinic performs well as a generic replacement for specialized matching algorithms in many programming-contest settings.

Push-Relabel

Push-relabel has the same broad worst-case family as Dinic in many presentations:

O(V²E)

but its practical behavior can be excellent, especially on dense graphs.

The algorithm does not search for full augmenting paths. It moves excess flow locally.

Its performance depends heavily on heuristics:

• highest-label selection
• gap relabeling
• global relabeling
• efficient active-vertex queues

A simple push-relabel implementation may be slower than Dinic. A tuned implementation can be very fast.

Graph Density

Graph density changes everything.

A sparse graph has:

E ≈ V

A dense graph has:

E ≈ V²

For Edmonds-Karp:

O(VE²)

Sparse case:

O(V³)

Dense case:

O(V⁵)

For Dinic:

O(V²E)

Sparse case:

O(V³)

Dense case:

O(V⁴)

This is one reason Edmonds-Karp is rarely used for large dense graphs.

Capacity Size

Capacity size affects algorithms differently.

Ford-Fulkerson depends on:

F

so large capacities can be dangerous.

Edmonds-Karp, Dinic, and push-relabel are strongly polynomial in the graph size for ordinary max flow. Their standard bounds do not depend directly on the numeric capacity values.

However, large capacities still affect implementation:

• use 64-bit integers
• avoid overflow in sums
• choose infinity carefully
• avoid multiplying flow and cost in 32-bit arithmetic

Min-Cost Flow

Min-cost flow is usually more expensive than max flow.

The successive shortest path method sends flow along cheapest residual paths.

If it augments one unit at a time, the number of augmentations may be:

F

Using Bellman-Ford for each shortest path:

O(FVE)

Using Dijkstra with potentials:

O(FE log V)

The potential-based version is usually preferred for sparse graphs.

If capacities are large and augmentations can push large bottlenecks, performance improves. If every augmentation pushes only one unit, cost can dominate.

Matching Complexity

Bipartite matching has special structure.

Algorithm	Complexity
Simple augmenting path	O(VE)
Hopcroft-Karp	O(E√V)
Dinic on unit network	O(E√V)

Use Hopcroft-Karp when the problem is exactly bipartite matching.

Use Dinic when the matching is part of a larger flow model.

Use min-cost flow when assignments have costs, quotas, or richer constraints.

Lower Bounds and Circulation

Lower-bound transformations add:

2

vertices for the super source and super sink, plus at most:

V

extra edges.

So the transformed graph has:

V' = V + 2
E' = E + O(V)

The asymptotic complexity remains essentially the complexity of the chosen max-flow algorithm on the transformed graph.

The transformation itself is linear:

O(V + E)

Node Splitting

Vertex-capacity and vertex-disjoint-path models often split every vertex.

This changes graph size to:

V' = 2V
E' = E + V

The graph remains linear in the size of the original graph.

But constants matter. If the original graph is already large, node splitting doubles memory usage and can noticeably increase runtime.

Memory Complexity

Most flow implementations use adjacency lists with explicit reverse edges.

Every logical edge creates two stored edges:

forward edge
reverse edge

Memory is:

O(V + E)

but the constant factor is roughly doubled.

For min-cost flow, each edge also stores cost.

For lower-bound recovery, you may also store original edge indices.

A typical edge structure contains:

to
reverse index
capacity
cost

or:

to
reverse index
capacity

for ordinary max flow.

Choosing an Algorithm

Use this decision guide:

Problem Type	Good Default
Small max-flow problem	Edmonds-Karp or Dinic
General max flow	Dinic
Dense max flow	Push-relabel
Bipartite matching	Hopcroft-Karp
Matching inside larger flow model	Dinic
Assignment with costs	Hungarian or min-cost flow
General costs and capacities	Min-cost flow with potentials
Lower bounds and demands	Circulation plus Dinic
Disjoint paths	Unit-capacity max flow

The best algorithm is not always the one with the strongest theoretical bound. Simplicity, correctness, and implementation reliability matter.

Practical Benchmarking

For production use, benchmark with realistic data.

Synthetic worst cases are useful, but real flow networks often have structure:

• layered graphs
• low degree
• many unit capacities
• skewed demands
• sparse eligibility edges
• repeated similar instances

An algorithm that looks inferior on paper may perform well on the actual workload.

Measure:

build time
solve time
memory use
number of augmentations or phases

For min-cost flow, also measure shortest-path iterations.

Common Mistakes

Comparing Bounds Without Graph Shape

O(V²E) and O(VE²) mean different things on sparse and dense graphs.

Ignoring Flow Value

Ford-Fulkerson can be fast when F is small and terrible when F is large.

Forgetting Transformation Costs

Node splitting, lower bounds, and time expansion can multiply graph size.

Using 32-Bit Arithmetic

Flow values, capacities, and total costs often exceed 32-bit limits.

Optimizing Too Early

A clear Dinic implementation is often sufficient. Start there unless the problem structure strongly suggests another algorithm.

Discussion

Complexity analysis for flow algorithms has two layers. The first is the algorithmic bound. The second is the modeling expansion required before the algorithm runs.

A scheduling problem may start with 100 workers and 50 shifts, but after time expansion, skill layers, and lower-bound constraints, the actual graph may contain thousands of nodes and edges. The complexity of the solver applies to that transformed graph, not the original problem statement.

This is why flow modeling and complexity analysis should be done together.

Takeaway

Analyze flow algorithms using graph size, edge count, flow value, capacity size, and model transformations. Ford-Fulkerson depends on flow value. Edmonds-Karp is predictable but often slow. Dinic is the standard general-purpose choice. Push-relabel is strong on dense networks. Hopcroft-Karp is specialized for bipartite matching. Min-cost flow is more expensive but more expressive.

Choose the simplest algorithm that comfortably fits the transformed graph you actually intend to solve.