12.15 Lower Bounds on Edges

Problem

A normal flow edge has only an upper capacity:

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

Many practical models need a minimum commitment as well.

A truck route may need at least 3 shipments per day to justify operating. A contract may require a supplier to deliver at least 100 units. A shift may require a minimum staffing level. A network reservation may require a baseline amount of bandwidth.

These requirements produce lower-bounded edges:

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

The difficulty is that lower bounds interact with flow conservation. Once an edge is forced to carry flow, its tail has already sent flow and its head has already received flow. The rest of the network must compensate for that imbalance.

Solution

Eliminate lower bounds by pre-sending the required amount of flow on every edge.

For each edge:

u -> v
lower = l
capacity = c

replace it with an ordinary edge:

u -> v
capacity = c - l

Then adjust vertex balances:

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

After all lower bounds are removed, solve the resulting imbalance using the circulation transformation from the previous recipe.

Why This Works

The lower bound says:

at least l units must travel from u to v

So we treat those l units as already sent.

That leaves only the optional part:

0 to c - l

The transformed edge decides how much extra flow travels beyond the required minimum.

At the end, recover the original flow:

f_original(u, v) = l(u, v) + f_extra(u, v)

Example

Original edge:

Edge	Lower	Capacity
A -> B	4	10

Transform it into:

Edge	Capacity
A -> B	6

Update balances:

Vertex	Balance
A	-4
B	+4

Interpretation:

• A has already sent 4 units.
• B has already received 4 units.
• The remaining problem must make the global flow consistent.

Multiple Edges

Suppose the graph contains:

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

Start all balances at zero.

Process A -> B:

balance[A] -= 3
balance[B] += 3

Process B -> C:

balance[B] -= 2
balance[C] += 2

Process A -> C:

balance[A] -= 1
balance[C] += 1

Final balances:

Vertex	Balance
A	-4
B	+1
C	+3

The sum is zero, as expected.

A has supplied 4 required units. B needs net 1 unit. C needs net 3 units.

Feasibility Check

After transforming all edges, build a super-source and super-sink graph.

For every vertex with positive balance:

SS -> v
capacity = balance[v]

For every vertex with negative balance:

v -> TT
capacity = -balance[v]

Then run max flow from SS to TT.

A feasible assignment exists if every edge leaving SS is saturated.

Example Feasibility Graph

From the previous balances:

Vertex	Balance
A	-4
B	+1
C	+3

Add:

Edge	Capacity
A -> TT	4
SS -> B	1
SS -> C	3

Then run max flow from SS to TT on the transformed graph.

If total flow equals:

1 + 3 = 4

the lower-bounded problem is feasible.

Lower-Bounded s-t Flow

Sometimes there is still a source s and sink t.

You may need to know whether there exists a flow from s to t satisfying all lower bounds.

The standard conversion is:

1. Remove lower bounds.
2. Add balances.
3. Add artificial edge:

t -> s
capacity = INF

4. Add super source and super sink.
5. Check whether all super-source edges are saturated.

The artificial edge allows flow conservation to be expressed as circulation.

Recovering the Flow Value

After solving the lower-bounded s-t problem, the flow on:

t -> s

represents the amount of s-t flow needed to close the circulation.

Depending on the formulation, this may be the feasible flow value or the baseline from which additional max-flow is computed.

For maximum feasible s-t flow:

1. First find any feasible circulation.
2. Remove SS, TT, and their incident edges.
3. Remove or fix the artificial edge t -> s.
4. Run ordinary max flow from s to t in the residual graph.
5. Add the additional flow to the feasible baseline.

Vertex Demands as Lower Bounds

Lower bounds on edges can also model vertex demands.

Suppose a department must receive at least 5 workers.

Add an edge from the department node to the sink:

department -> t
lower = 5
capacity = maxAllowed

The lower bound enforces minimum staffing.

Similarly, a supplier that must ship at least 10 units can be represented by an edge:

s -> supplier
lower = 10
capacity = maxSupply

This style keeps all constraints inside the flow graph.

Implementation Recipe

For each original edge, store:

type EdgeSpec struct {
    From     int
    To       int
    Lower    int64
    Capacity int64
}

Transform:

extraCapacity = Capacity - Lower

addEdge(From, To, extraCapacity)

balance[From] -= Lower
balance[To]   += Lower

Then add super edges:

if balance[v] > 0:
    addEdge(SS, v, balance[v])

if balance[v] < 0:
    addEdge(v, TT, -balance[v])

After max flow, recover:

flowOriginal = Lower + flowExtra

Keep an index from each original edge to its transformed edge so recovery is direct.

Invalid Inputs

Reject an edge immediately if:

lower > capacity

No feasible solution can satisfy it.

Also check that all values use the same unit. Mixing daily capacity with hourly demand creates a model that may be mathematically feasible but practically meaningless.

Complexity

The lower-bound transformation is linear:

O(V + E)

It adds:

• 2 vertices
• at most V super edges
• optional artificial edge t -> s

The dominant cost is the max-flow algorithm used afterward.

Common Mistakes

Treating Lower Bound as Extra Capacity

The transformed capacity is:

capacity - lower

not:

capacity + lower

Forgetting Balance Updates

Lower bounds are not removed just by shrinking capacity. They also create vertex imbalance.

Saturation Check on the Wrong Edges

Feasibility requires saturating all edges out of SS, not all original edges.

Losing the Mapping to Original Edges

Store edge indices. Otherwise reconstructing the final original flow becomes error-prone.

Using INF Too Small

For t -> s, INF must exceed any feasible total flow. A safe choice is often the sum of capacities leaving s, using 64-bit integers.

Discussion

Lower bounds are a modeling feature, not a separate family of algorithms. They let you express minimum obligations while still using ordinary max-flow machinery. The transformation works because every lower bound can be viewed as flow that has already been committed, leaving only residual optional capacity to decide.

Most bugs in lower-bounded flow code come from sign errors in the balance array or from forgetting that the computed flow is only the extra flow above the lower bound.

Takeaway

To handle lower bounds, pre-send the required flow on each edge, reduce the capacity by the lower bound, and record the resulting balance at each endpoint. Then use a super source and super sink to determine whether the imbalances can be repaired.

This reduction turns lower-bounded flow problems into ordinary max-flow feasibility problems while preserving the ability to recover the original edge flows.