12.14 Circulation with Demands

Problem

So far, flow networks have had a source and a sink. Flow starts at s, moves through the graph, and ends at t.

Many real systems are not organized that way.

A supply network may contain several producers and several consumers. A transportation system may require certain minimum shipments on specific routes. A scheduling model may require every department to receive a fixed amount of coverage. A logistics graph may have lower and upper bounds on each connection.

In these problems, the question is not always:

How much can we send from s to t?

The question is often:

Can we assign flows to all edges so that every local requirement is satisfied?

This is the circulation problem.

Solution

Use a flow model with lower bounds, upper bounds, and vertex balance constraints.

Each edge has:

lower(u, v) ≤ flow(u, v) ≤ capacity(u, v)

The lower bound says that at least that much flow must use the edge.

A circulation has no special source or sink. Instead, every vertex must satisfy conservation:

incoming flow = outgoing flow

When vertices have supplies or demands, we convert those requirements into an ordinary maximum-flow instance using a super source and a super sink.

Basic Circulation

In a pure circulation problem, every vertex conserves flow.

Example:

A -> B
B -> C
C -> A

If each edge carries 5 units, every vertex receives 5 and sends 5.

This is a circulation.

Unlike maximum flow, no vertex is designated as the global origin or destination.

Lower and Upper Bounds

A bounded edge has two values:

Symbol	Meaning
l(u, v)	Lower bound
c(u, v)	Upper capacity

The valid flow range is:

l(u, v) ≤ f(u, v) ≤ c(u, v)

Example:

Edge	Lower	Capacity
A -> B	3	10

The edge must carry at least 3 units and at most 10 units.

This is common in contracts, scheduling, and logistics.

Removing Lower Bounds

Lower bounds make the problem awkward because every edge starts with an obligation.

The standard trick is to satisfy each lower bound immediately.

For every edge:

u -> v

with lower bound l and capacity c, define a residual capacity:

c' = c - l

Then record the balance effect:

balance[u] -= l
balance[v] += l

Interpretation:

• u has already sent l units.
• v has already received l units.
• The remaining adjustable capacity is c - l.

After this transformation, every edge has lower bound zero.

Example

Edge:

Edge	Lower	Capacity
A -> B	3	10

Replace it with:

Edge	Capacity
A -> B	7

Update balances:

Vertex	Balance Change
A	-3
B	+3

Now the max-flow part only decides how much additional flow, from 0 to 7, should travel from A to B.

Balance Interpretation

After removing all lower bounds, each vertex has a balance.

Use this convention:

Balance	Meaning
Positive	Vertex has excess demand to absorb
Negative	Vertex has excess supply to send

If:

balance[v] > 0

then vertex v needs that much incoming flow.

If:

balance[v] < 0

then vertex v must send out -balance[v] units.

Feasibility Transformation

To test whether a feasible circulation exists:

1. Remove lower bounds.
2. Compute vertex balances.
3. Add a super source SS.
4. Add a super sink TT.
5. For every vertex with positive balance, add:

SS -> v
capacity = balance[v]

6. For every vertex with negative balance, add:

v -> TT
capacity = -balance[v]

7. Run max flow from SS to TT.
8. A feasible circulation exists if all edges out of SS are saturated.

This converts circulation feasibility into ordinary max flow.

Small Example

Original edges:

Edge	Lower	Capacity
A -> B	3	8
B -> C	2	6
C -> A	1	5

Remove lower bounds:

Edge	New Capacity
A -> B	5
B -> C	4
C -> A	4

Balances:

Vertex	Calculation	Balance
A	-3 + 1	-2
B	+3 - 2	1
C	+2 - 1	1

Add:

Edge	Capacity
A -> TT	2
SS -> B	1
SS -> C	1

If max flow can send 2 units from SS to TT, then the original bounded circulation is feasible.

Recovering Original Flows

After max flow succeeds, recover each original edge flow by adding back its lower bound.

For each original edge:

originalFlow(u, v) = lower(u, v) + computedFlow(u, v)

Example:

Edge	Lower	Computed Extra	Original Flow
A -> B	3	2	5
B -> C	2	0	2

The returned flow now respects all lower and upper bounds.

Circulation with Supplies and Demands

Some models attach supply or demand directly to vertices.

Example:

Vertex	Requirement
Factory	supply 10
Store A	demand 4
Store B	demand 6

You can represent this with balances directly.

One common convention:

Vertex Type	Balance
Supply vertex	negative
Demand vertex	positive

Then use the same super-source and super-sink transformation.

Feasibility Condition

Before running max flow, the total balance must sum to zero.

sum(balance[v]) = 0

If not, feasibility is impossible.

The network cannot consume more flow than it produces, and it cannot produce more flow than it consumes.

This is an inexpensive early check.

Converting s-t Flow with Lower Bounds

Suppose you want to send flow from s to t, but edges have lower bounds.

Add an artificial edge:

t -> s
capacity = INF

Then solve circulation with lower bounds.

This edge closes the loop and allows the circulation machinery to handle the source and sink requirements.

After feasibility is established, the flow on t -> s represents the amount sent from s to t.

Minimum Feasible Flow

Sometimes the problem asks for the smallest feasible flow from s to t.

Use the circulation transformation with edge:

t -> s

Then minimize the flow on that edge, often by running additional residual adjustments or binary search depending on the formulation.

Maximum Feasible Flow

For maximum feasible flow with lower bounds:

1. Check feasibility using circulation.
2. Remove the artificial super source and super sink.
3. Run additional max flow from s to t in the residual graph.
4. Add that value to the already feasible flow.

This separates feasibility from optimization.

Common Applications

Shipment Contracts

A supplier must send at least a contracted minimum along certain routes, but cannot exceed route capacity.

Workforce Scheduling

Each shift must receive a minimum number of workers, while workers have maximum availability.

Course Allocation

Courses may require minimum enrollment and have maximum capacity.

Traffic Engineering

Certain links must carry required baseline traffic while respecting bandwidth limits.

Production Planning

Factories have supply limits, warehouses have throughput limits, and customers have fixed demand.

Implementation Pattern

Store each original edge with:

from
to
lower
capacity
edgeIndex

When building the transformed graph:

addEdge(from, to, capacity - lower)
balance[from] -= lower
balance[to] += lower

After solving, read the residual state of the transformed edge and add lower back.

Keep artificial edges separate so they do not appear in the final answer.

Complexity

The transformation adds:

2

vertices and at most:

V

extra edges.

The running time is essentially the running time of the max-flow algorithm used.

With Dinic:

O(V²E)

in the general case, with the transformed graph size.

In practice, the transformation overhead is small.

Common Mistakes

Forgetting to Subtract Lower Bounds

The transformed capacity must be:

capacity - lower

not the original capacity.

Reversing Balance Signs

Pick one sign convention and use it consistently. A common convention is: lower-bound flow subtracts from the tail and adds to the head.

Checking Only Total Flow

Feasibility requires all edges from the super source to be saturated. A nonzero flow is not enough.

Forgetting to Restore Lower Bounds

The flow computed on transformed edges is only the extra flow beyond the lower bound.

Using Too Small an Infinity

For artificial edges such as t -> s, choose an upper bound at least as large as the maximum possible total flow in the model.

Discussion

Circulation with demands is the standard way to handle flow problems that have local obligations. Lower bounds represent required movement. Vertex balances represent supply and demand. Super source and super sink edges convert those obligations into an ordinary max-flow feasibility test.

This technique is a modeling tool more than a new algorithm. Once the transformation is correct, the rest is ordinary max flow.

Takeaway

Circulation removes the special role of source and sink and asks whether all local flow requirements can be satisfied. Lower bounds are handled by pre-sending required flow, recording vertex balances, and using a super source and super sink to repair the imbalance.

A feasible circulation exists exactly when the max-flow computation saturates every edge leaving the super source.