Much power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or minimum cut in a directed graph.

The Problem: Circulation with Demands. In this case, we suppose that there can be a set S of sources generating flow, and a set T of sinks that can absorb flow and all edges have capacities. Our goal is to ship flow from nodes with available supply to those with given demands. We are given a flow network with capacities on the edges. Now associated with each node is a demand, if the demand for a node is > 0, then that node has a demand for flow and vice versa. And if d=0, the node is neither a sink nor a source. We use two sets: S for nodes with negative demand and set T for nodes with positive demand. Now instead of considering a maximization problem, we are concerned with a feasibility problem. We want to know whether there exists a circulation that meets the capacity and demand conditions. For a feasible circulation to exist, the total supply must equal the total demand. Proof on page 380.

Designing and Analyzing an Algorithm for Circulations. We can reduce the problem of finding a feasible circulation with demands to the problem of finding a maximum s-t flow in a different network. We attach a super-source s* to each node in S, and a super-sink t* to each node in T. Specifically, we create a graph G' from G by adding new nodes s* and t* to G. In this graph G', we will be seeking a maximum s*-t* flow. Note that there cannot be an s*-t* flow in G' of value greater than D.In summary, there is a feasible circulation with demands in G if and only if the max s*-t* flow in G' has value D. We have to let our algorithm decide which source will supply the flow to which sink. Am more difficult problem is the Multicommodity Flow Problem where every source has a respective sink it supplies with flow.

The Problem: Circulations with Demands and Lower Bounds. In many applications we also want to satisfy demands at various nodes; we also want to force the flow to make use of certain edges. This can be done by placing lower bounds on edges. As before each node will have a demand, a capacity, plus a lower bound(integers) that means that the flow value of a certain edge must be at least the lower bound. As before we wish to decide whether there exists a feasible circulation that satisfies the defined capacity and demand conditions on page 383.

Designing and Analyzing an Algorithm with Lower Bounds. Our strategy will be to reduce this to the problem of finding a circulation with demands but no lower bounds. We know that we need to send at least l units of flow on each edge. This flow satisfies all the capacity conditions but does not satisfy all the demand conditions. We can claim that there is a feasible circulation in G if and only if there is a feasible circulation in G'. If all demands, lower bounds, and capacities in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued.

This section was a bit difficult to understand compared to the sections prior to it, I give it a 7.5/10 scale.