Question

Suppose that each source si in a multisource, multisink problem produces exactly pi units of flow, so that f(si, = pi. Suppose also that each sink tj consumes exactly qj units, so that f(V, tj) = qj, where Li Pi = £; 9;. Show how to convert the problem of finding a flow f that obeys these additional constraints into the problem of finding a maximum flow in a single-source, single-sink flow network.

Answer 1

Let there be multiple sources and sinks, the capacity of sources being $p_i$ and that of sinks be $q_j$ . To find the maximum flow in the given graph, modify it as follows to then use single source and sink flow algorithm.

Create a new source, let it be S, and add an edge from S to each original source $s_i$ with the edge weight $p_i$ . Similarly, create a new sink T, and add an from $t_i$ to T with edge weight $q_i$ . Keep other things the same as the original graph.

Claim: The max flow in this new graph will correspond to the maximum flow in the original graph while obeying the flow constraints on each source and sink.

Proof: From the new source S, there is an edge to $s_i$ with capacity $p_i$ , hence the flow from S to $s_i$ cannot be more than $p_i$ . Similarly the flow from $t_i$ to T cannot be more than $q_i$ . Therefore the original constraints are being satisfied. As other edges are from the original graph, the remaining flow constraints will automatically be satisfied. Hence, the maximum flow on the new graph will correspond to the maximum flow in the original graph, while also satisfying the constraints of the original sources and sinks.

Comment in case of any doubts.