Graph algorithms / interactive lesson

Feasible Flow with Lower Bounds

Decide whether a network with lower and upper edge bounds has an s-t flow of value at least k by reducing it to feasible circulation and then to one auxiliary max-flow test.

University Guided lesson

Lower-bound feasible s-t flow

Existence of flow value at least k

Step 1 / 13problem

problem

Do we have an s-t flow of value at least 6?

Every edge has a lower and upper bound. We must route flow from s to t, conserve flow at internal vertices, respect all bounds, and reach value at least k.

The lower bounds make this harder than ordinary max flow because every edge may already require some mandatory flow.

Aux flow

0/4

v	in l	out l	d
S	6	2	4
A	2	2	0
B	1	2	-1
T	3	6	-3

Criterion: all edges out of SS must be saturated. If yes, the circulation exists, so the original lower-bound network has an s-t flow of value at least k.

About the algorithm

The problem asks whether a directed network with lower and upper edge bounds has an s-t flow of value at least k. The standard solution reduces it to a feasible circulation test with lower bounds, then to one ordinary max-flow computation.

Close the flow

Add a return edge from t to s with lower bound k. If a feasible circulation uses that edge, the original network carries the same amount from s to t, and the lower bound guarantees value at least k.

Remove lower bounds

Reserve the lower bound on every edge and reduce its capacity to u-l. These reserved amounts may leave vertices with too much mandatory inflow or outflow, measured by demand(v)=lowerIn(v)-lowerOut(v).

Auxiliary max flow

Add a super-source to every positive-demand vertex and a super-sink from every negative-demand vertex. The lower-bound circulation exists exactly when max flow saturates all edges leaving the super-source.

Code companion

Connect each visual decision to an implementation pattern.

// Is there an s-t flow of value at least k?
add edge (t, s) with lower k and upper large enough

for each edge e = (u, v) with bounds [l, c]:
  capacity'(e) = c - l
  demand[u] -= l
  demand[v] += l

create super-source SS and super-sink TT
for each vertex v:
  if demand[v] > 0: add edge SS -> v with capacity demand[v]
  if demand[v] < 0: add edge v -> TT with capacity -demand[v]

run max-flow from SS to TT
return all SS edges are saturated