Advanced Flow Networks, in depth: vertex capacities, circulations with demands, lower bounds and min flow

The reduction mindset

A flow network is a directed graph with a capacity c(u, v) on each edge, a source s and a sink t. A flow assigns f(u, v) with 0 ≤ f ≤ c on every edge and conservation at every node other than s and t: inflow equals outflow. The max-flow min-cut theorem says the largest flow value equals the smallest capacity of an s-t cut, and when capacities are integers there is an integral maximum flow, which augmenting-path algorithms find.

Every reduction below follows the same discipline. First, transform the input graph. Second, prove a two-way correspondence: every valid solution of the original problem maps to a flow of a known value in the new graph, and every such flow maps back. Third, translate the answer, including the per-edge flows, back to the original. Skipping the third step is where most bugs live: the transformed graph has extra edges whose flow means nothing to the caller.

All of the code here uses a small Dinic solver whose add method returns a handle to the forward edge, so flows can be read back. Any max-flow implementation works; Dinic's algorithm is a good default because it is fast on the unit-capacity graphs these reductions often produce.

Multiple terminals, undirected edges and vertex capacities

Multiple sources and sinks. Add a super-source S with an edge S to each source s_i, and a super-sink T with an edge from each sink t_j. Give these edges infinite capacity if sources are unlimited, or capacity equal to each source's supply if it is bounded. Any flow in the original with multiple sources is a flow from S to T, and vice versa, because S and T only add conservation-free endpoints. This is the move that makes bipartite matching a flow problem.

Undirected edges. Replace an undirected edge {u, v} with capacity c by two directed edges u to v and v to u, each with capacity c. A flow could then send flow both ways at once, but any such flow can be cancelled down to a one-way flow of the net amount without changing any node's balance, so the maximum is unaffected.

Vertex capacities. If a node v can pass at most k units, split it into v_in and v_out, joined by an edge of capacity k. All edges that entered v now enter v_in; all that left v now leave v_out. Every unit through v crosses the internal edge, so the limit holds, and nothing else changes. The node count doubles and the edge count grows by n.

def split_vertices(n, edges, vcap, s, t):
    """edges: (u, v, cap). vcap[v] = throughput limit or None.
    Node v becomes v_in = 2v and v_out = 2v + 1."""
    INF = float("inf")
    d = Dinic(2 * n)
    for v in range(n):
        d.add(2 * v, 2 * v + 1, INF if vcap[v] is None else vcap[v])
    for u, v, cap in edges:
        d.add(2 * u + 1, 2 * v, cap)       # leave u_out, enter v_in
    return d.maxflow(2 * s, 2 * t + 1)    # start at s_in, finish at t_out

Vertex splitting is how to count vertex-disjoint paths: give every internal node capacity 1 and every edge capacity 1, and the max flow is the number of s-t paths that share no intermediate node. By Menger's theorem it also equals the fewest nodes whose removal disconnects s from t, which is the standard way to measure how many router or service failures a network survives. Without splitting, unit edge capacities give edge-disjoint paths instead.

Circulations with demands

A circulation with demands drops s and t. Each node v has a demand d(v): positive means v consumes that much, negative means it supplies that much, and the demands sum to zero. The question is whether some flow within capacities satisfies every node: inflow minus outflow equals d(v).

The reduction adds a super-source S with an edge S to v of capacity -d(v) for each supplier, and a super-sink T with an edge v to T of capacity d(v) for each consumer. Let D be the total supply. A feasible circulation exists exactly when the max flow from S to T equals D, that is, when every edge out of S is saturated. If it is less, the minimum cut names the obstruction: a set of nodes whose demand exceeds what edge capacities can bring in, such as "these warehouses need 140 units and only 120 can reach them".

Lower bounds become demands

Now suppose edge (u, v) has a lower bound l as well as capacity c: its flow must lie in [l, c]. Minimum staffing per shift, a contract that commits a carrier to a minimum volume, a pipe that must keep some flow to avoid freezing. Lower bounds turn into demands.

Imagine pre-sending l units along the edge. That uses up l of its range, so the remaining adjustable amount is in [0, c - l]. It also unbalances the endpoints: v has received l units it must pass on, and u has sent l units it must receive from somewhere. Record this as an excess: excess(v) += l and excess(u) -= l. After processing every edge, a node with positive excess has extra inflow to dispose of; a node with negative excess needs more inflow.

For a circulation, connect S to every node with positive excess (capacity = excess) and every node with negative excess to T (capacity = -excess), and solve. For an s-t flow with lower bounds, first add an edge t to s with infinite capacity: this converts the s-t flow into a circulation, because whatever leaves s and reaches t can return along it. Then do the same S and T construction. A feasible flow exists if and only if the S-T max flow saturates every edge out of S. Final per-edge flow is l plus the flow on the transformed edge.

Maximum and minimum flow with lower bounds

Finding a feasible flow is the first phase. To find the maximum s-t flow subject to the bounds, read the flow on the t-to-s edge (that is the value of the feasible flow), then delete the t-to-s edge and every S and T edge, and augment from s to t in the residual graph that remains. The residual graph still encodes the lower bounds, because their pre-sent flow is baked into the excesses that the first phase already satisfied. For the minimum flow, do the same deletion, then push as much as possible from t back to s, and subtract.

def max_flow_with_bounds(n, edges, s, t):
    """edges: (u, v, low, cap). Returns (value, per-edge flows) or None if infeasible."""
    S, T = n, n + 1
    d = Dinic(n + 2)
    excess = [0] * n
    handles = []
    for u, v, low, cap in edges:
        if low > cap:
            return None
        handles.append(d.add(u, v, cap - low))
        excess[v] += low
        excess[u] -= low
    ts = d.add(t, s, float("inf"))         # s-t flow becomes a circulation
    need = 0
    for v in range(n):
        if excess[v] > 0:
            d.add(S, v, excess[v]); need += excess[v]
        elif excess[v] < 0:
            d.add(v, T, -excess[v])
    if d.maxflow(S, T) != need:
        return None                        # some lower bound cannot be met
    u, i = ts
    rev = d.g[u][i][2]
    base = d.g[s][rev][1]                  # flow on t->s, read from its reverse edge
    d.g[u][i][1] = d.g[s][rev][1] = 0      # delete t->s in both directions
    for e in d.g[S]:                        # delete S edges
        e[1] = d.g[e[0]][e[2]][1] = 0
    for e in d.g[T]:                        # delete T edges (reverse side lists them)
        e[1] = d.g[e[0]][e[2]][1] = 0
    extra = d.maxflow(s, t)
    flows = [low + d.g[d.g[u][i][0]][d.g[u][i][2]][1]
             for (u, i), (_, _, low, _) in zip(handles, edges)]
    return base + extra, flows

Here an edge is stored as [to, residual_cap, index_of_reverse], and the flow on a forward edge equals the residual capacity of its reverse. The minimum-flow variant is identical up to the deletion step, then returns base - d.maxflow(t, s).

Worked example. Take Figure 1: s to a [0,4], s to b [0,3], a to b [2,3], a to t [1,2], b to t [3,4]. Excesses: a sends 2 + 1 of pre-sent flow so excess(a) = -3; b receives 2 and sends 3 so excess(b) = -1; t receives 1 + 3 so excess(t) = +4. Phase one sends 4 units S to t, around t to s, then s to a to T (3) and s to b to T (1). All of S's capacity is used, so the bounds are feasible, and the feasible flow has value 4. After deleting the helper edges, the residual graph has s to a with 1 left, s to b with 2, and a to t and b to t with 1 each, so two more units augment along s-a-t and s-b-t. The maximum is 6, with edge flows 4, 2, 2, 2, 4; check that a and b each pass 4 in and 4 out. No augmenting path runs from t back to s after phase one, because every edge into t is at its lower bound, so the minimum is 4. Brute-force enumeration of every integer flow on this graph gives the same 6 and 4.

Modelling with bounds

Matrix rounding. Given a matrix of non-negative reals whose row and column sums are integers, round every entry up or down so that all row and column sums are preserved. Build a node per row and per column, an edge from s to row i with bounds [floor(r_i), ceil(r_i)], an edge row i to column j with bounds [floor(a_ij), ceil(a_ij)], and column j to t likewise. A feasible fractional flow exists (the matrix itself), so by integrality a feasible integral one does too, and it is the rounding. Statistical agencies use this to round published tables consistently.

Shift staffing. Shift edges carry [minimum staff, maximum staff] and worker edges [contracted minimum, maximum hours]. Feasibility asks whether the roster can be filled, and minimum flow gives the smallest staffing that meets every minimum.

When edges also have costs per unit, the same lower-bound transformation feeds a minimum-cost flow solver instead; the reduction is unchanged, only the solver differs. Cut-based models such as project selection are covered in the max-flow min-cut theorem, and the unit-capacity special case in bipartite matching.

Failure modes

• Forgetting to delete the t-to-s edge before the second phase. The solver then pushes flow from s to t and straight back around, reporting an inflated or infinite maximum. This is the classic bug in lower-bound code.
• Leaving S and T edges in place. Residual capacity on them lets phase two undo the lower bounds, so some edges end below l. Always validate the returned flows against every bound.
• Reading per-edge flow from the transformed edge without adding l back. The answer looks feasible and is wrong by exactly the lower bounds.
• Checking feasibility by comparing to the wrong total. Compare the S-T flow with the sum of positive excesses, not the sum of lower bounds; they differ whenever a node has both incoming and outgoing bounds.
• Using float('inf') with an integer-only solver. Use a large integer bigger than the sum of finite capacities.
• Assuming a unique answer. Many flows achieve the optimum; tests should check value, bounds and conservation, not one edge assignment.

A linear-time certificate catches most of these: check every edge flow lies in [l, c], conservation holds at every node other than s and t, and the value equals net outflow at s.

What to do next

1. Implement the lower-bound reduction on top of your existing max-flow code, with a validator that checks bounds and conservation.
2. Reproduce the worked example: feasible value 4, maximum 6, minimum 4.
3. Write a brute-force enumerator for graphs with five or six edges and compare it to your solver on thousands of random bounded instances.
4. Model one real allocation problem you have, such as rostering, quotas or routing with minimums, and print the minimum cut when it is infeasible.
5. Use vertex splitting to count vertex-disjoint paths between two nodes in a service graph you operate.
6. Next, study minimum-cost flow, which reuses every reduction here with a different solver.