Circulation with Lower Bounds

Why Lower Bounds Change the Starting Point

Ordinary maximum flow starts from the all-zero solution. That works because every edge permits zero flow. A lower bound removes that convenience: if a contract requires at least two units on an edge, zero is illegal before the algorithm even begins.

Lower Bounds and the Balance Ledger

Each directed edge $(u,v)$ has lower bound $\ell(u,v)$ and upper bound $c(u,v)$:

A circulation must also conserve flow at every vertex:

The reduction first commits every lower bound by writing $f(u,v)=\ell(u,v)+x(u,v)$. The new variable $x$ is the extra flow we may still choose, with capacity $0\le x(u,v)\le c(u,v)-\ell(u,v)$.

Define the committed imbalance using one fixed sign convention:

The Super-Source Reduction

Create a new source $S^*$ and sink $T^*$. Keep each original edge with residual capacity $c-\ell$, then connect the balance ledger to the two auxiliary vertices.

flowchart TD
    L[Commit every lower bound] --> B[Compute each balance b]
    B --> A[Add residual capacities and auxiliary edges]
    A --> F[Run max flow from S* to T*]
    F --> Q{Every S* edge saturated?}
    Q -->|Yes| Y[Feasible circulation]
    Q -->|No| N[No feasible circulation]

1. For each bounded edge $(u,v,\ell,c)$, add an ordinary edge $u\to v$ of capacity $c-\ell$.
2. Update $b(u)\mathrel{-}=\ell$ and $b(v)\mathrel{+}=\ell$.
3. If $b(v)>0$, add $S^*\to v$ with capacity $b(v)$ and add that amount to the required auxiliary flow.
4. If $b(v)<0$, add $v\to T^*$ with capacity $-b(v)$.
5. Run max flow from $S^*$ to $T^*$. Feasibility is equivalent to sending the full required amount.

Worked Example: Repairing the Triangle

For the three-edge network above, the lower-bound ledger is:

Add the repair flow back to the committed lower bounds:

The final circulation sends two units around the entire triangle. Every vertex now receives two and sends two, so conservation and all edge bounds hold simultaneously.

Turning a Bounded $s$–$t$ Flow into a Circulation

A normal $s$–$t$ flow intentionally violates conservation at two vertices: $s$ has net outflow and $t$ has net inflow. Close that accounting loop by adding an artificial edge $t\to s$ with lower bound $0$ and a safely large upper bound, then run the same circulation-feasibility reduction.

For a maximum feasible bounded $s$–$t$ flow, record the current flow $F_0$ on the artificial $t\to s$ edge. Disable that edge and its paired reverse residual edge, remove $S^*$ and $T^*$, then run ordinary max flow from $s$ to $t$ on the remaining residual network. If that run adds $\Delta$, the answer is $F_0+\Delta$.

Why Saturation Proves Feasibility

The reduction preserves each requirement for a different reason:

If the maximum auxiliary flow is smaller than $\sum_{b(v)>0}b(v)$, some committed excess cannot reach the deficits through residual capacity. No different arrangement can satisfy all lower bounds, upper bounds, and conservation: the max-flow/min-cut theorem supplies the obstruction.

Implementation: Build the Reduction Carefully

The reusable code is not a new max-flow algorithm. It is a wrapper that converts bounded edges into ordinary residual edges and a balance array, then calls an existing max-flow implementation.

def add_bounded_edge(graph, balance, u, v, lower, upper):
    if lower > upper:
        raise ValueError("lower bound exceeds upper bound")
    add_edge(graph, u, v, upper - lower)
    balance[u] -= lower
    balance[v] += lower

def attach_super_nodes(graph, balance, super_source, super_sink):
    required = 0
    for vertex, value in enumerate(balance):
        if value > 0:
            add_edge(graph, super_source, vertex, value)
            required += value
        elif value < 0:
            add_edge(graph, vertex, super_sink, -value)
    return required

# feasible iff max_flow(graph, super_source, super_sink) == required

using int64 = long long;

void addBoundedEdge(int u, int v, int64 lower, int64 upper,
                    vector<int64>& balance) {
    if (lower > upper) throw invalid_argument("invalid bounds");
    addEdge(u, v, upper - lower);
    balance[u] -= lower;
    balance[v] += lower;
}

int64 attachSuperNodes(const vector<int64>& balance,
                       int superSource, int superSink) {
    int64 required = 0;
    for (int v = 0; v < (int)balance.size(); ++v) {
        if (balance[v] > 0) {
            addEdge(superSource, v, balance[v]);
            required += balance[v];
        } else if (balance[v] < 0) {
            addEdge(v, superSink, -balance[v]);
        }
    }
    return required;
}

static void addBoundedEdge(int u, int v, long lower, long upper,
                           long[] balance) {
    if (lower > upper) throw new IllegalArgumentException("invalid bounds");
    addEdge(u, v, upper - lower);
    balance[u] -= lower;
    balance[v] += lower;
}

static long attachSuperNodes(long[] balance,
                             int superSource, int superSink) {
    long required = 0;
    for (int v = 0; v < balance.length; v++) {
        if (balance[v] > 0) {
            addEdge(superSource, v, balance[v]);
            required += balance[v];
        } else if (balance[v] < 0) {
            addEdge(v, superSink, -balance[v]);
        }
    }
    return required;
}

The snippets assume addEdge creates the usual paired forward and reverse residual edges. Keep the original lower bound alongside the residual edge so final flow can be reconstructed as $\ell+x$.

Minimum Commitments in Real Networks

Lower bounds represent promises, minimum service levels, or obligations; upper bounds represent physical or policy limits.

Feasibility answers only “can every commitment be honored?” If multiple feasible circulations have different prices, add costs and solve a minimum-cost circulation or flow after applying the same lower-bound transformation.

Diagnosing an Infeasible Instance

A failed max-flow run is useful evidence, not merely a boolean result. Vertices reachable from $S^*$ in the final residual graph define a cut: the original residual edges crossing that cut do not have enough capacity to transport all committed excess toward the required deficits.

Complexity, Limits, and When to Use It

The transformation adds exactly two vertices and at most one auxiliary edge per original vertex. With $V'=V+2$ and $E'=E+O(V)$, runtime is dominated by the chosen max-flow engine on the transformed graph. Reconstruction is linear in the number of original edges.