Flow with Lower and Upper Bounds

Before reading this article, please read Maximum Flow and ensure you are proficient with maximum flow algorithms.

Overview

The lower-upper bound flow problem essentially assigns a flow upper bound \(c(u,v)\) and a flow lower bound \(b(u,v)\) to each edge of the flow network. That is, a feasible flow must satisfy \(b(u,v) \leq f(u,v) \leq c(u,v)\). Additionally, flow conservation must hold for all nodes except the source and sink.

Depending on the problem requirements, we can use lower-upper bound flow to solve different problems.

Feasible Flow with Lower and Upper Bounds (No Source/Sink)

Given a flow network \(G\) without source and sink. Determine whether there exists a way to assign flow to each edge such that every edge satisfies its lower and upper bounds and every node satisfies flow conservation.

Assume each edge already carries a flow of \(b(u,v)\), treating it as the initial flow. Meanwhile, we add an edge from \(u\) to \(v\) with capacity \(c(u,v) - b(u,v)\) in a new graph. Consider adjusting the flow in this new graph.

Since a maximum flow must satisfy the initial flow conservation condition (maximum flow can be viewed as a lower-upper bound flow with lower bound \(0\)), the constructed initial flow may not satisfy flow conservation. Let \(M\) be the initial inflow minus initial outflow at a node.

If \(M=0\), flow conservation holds, no additional edge is needed.

If \(M>0\), inflow is too large. Create an additional source \(S'\), and connect \(S'\) to this node with an edge of capacity \(M\).

If \(M<0\), outflow is too large. Create an additional sink \(T'\), and connect this node to \(T'\) with an edge of capacity \(-M\).

If the additional edge is saturated, it means the flow conservation condition for this node can be satisfied; otherwise, it cannot. (Because the original graph plus the additional flow will satisfy flow conservation in the original graph.)

After constructing the graph, run a maximum flow from \(S'\) to \(T'\). If all edges from \(S'\) are saturated, a feasible flow exists; otherwise, it does not.

Feasible Flow with Lower and Upper Bounds (With Source/Sink)

Given a flow network \(G\) with source and sink. Determine whether there exists a way to assign flow to each edge such that every edge satisfies its lower and upper bounds and every node except the source and sink satisfies flow conservation.

Let the source be \(S\) and the sink be \(T\).

We can add an edge from \(T\) to \(S\) with upper bound \(\infty\) and lower bound \(0\), transforming it into a feasible flow problem without source/sink.

If a solution exists, the feasible flow from \(S\) to \(T\) equals the flow on the additional edge from \(T\) to \(S\).

Maximum Flow with Lower and Upper Bounds (With Source/Sink)

Given a flow network \(G\) with source and sink. Determine whether there exists a way to assign flow to each edge such that every edge satisfies its lower and upper bounds and every node except the source and sink satisfies flow conservation. If it exists, find the maximum flow satisfying the assignment.

First, find any feasible flow on the network. If none exists, we can terminate.

Otherwise, consider the residual network after removing all additional edges and adjust the flow on it.

Run a maximum flow from \(S\) to \(T\) once more on the residual network. The sum of the feasible flow and this maximum flow is the answer.

A Very Common Mistake

The maximum flow from \(S\) to \(T\) should be run on the residual network obtained after solving the feasible flow with lower-upper bounds.

Never run it on the original flow network.

Minimum Flow with Lower and Upper Bounds (With Source/Sink)

Given a flow network \(G\) with source and sink. Determine whether there exists a way to assign flow to each edge such that every edge satisfies its lower and upper bounds and every node except the source and sink satisfies flow conservation. If it exists, find the minimum flow satisfying the assignment.

Similarly, we consider removing unnecessary flow from the residual network.

First, find any feasible flow on the network. If none exists, we can terminate.

Otherwise, consider the residual network after removing all additional edges.

Run a maximum flow from \(T\) to \(S\) once more on the residual network. Subtract this maximum flow from the feasible flow to get the answer.

AHOI 2014 Side Story

For each story edge from \(x\) to \(y\) with cost \(v\), set the upper bound to \(\infty\) and the lower bound to \(1\).

For each node, connect it to \(T\) with cost \(c\), upper bound \(\infty\), and lower bound \(1\).

Let node \(1\) be the source \(S\).

Run a minimum-cost feasible flow with lower-upper bounds and source/sink once.

Since the solution for minimum-cost feasible flow is similar to minimum feasible flow, it is not elaborated here.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用