In a standard s ? t Maximum-Flow Problem, we assume edges have capacities, and t
ID: 3708422 • Letter: I
Question
In a standard s ? t Maximum-Flow Problem, we assume edges have capacities, and there is no limit on how much flow is allowed to pass through a node. In this problem, we consider a variant of the Maximum-Flow and Min-Cut problems with node capacities.
Let G = (V, E) be a directed graph, with source s ? V , sink t ? V , and nonnegative node capacities cv ?0 for each v?V. Given a flow f in this graph,the flow through node v is defined as fin(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: fin(v) ? cv for all nodes.
Give a polynomial-time algorithm to find an s ? t maximum flow in such a node-capacitated network. Define an s?t cut for node-capacitated networks, and show that the analogue of the Max-Flow Min-Cut Theorem holds true.
Explanation / Answer
Given a graph G with node capacities we reduce the problem to one with edge capacities in a new graph G? as follows. For each node u in G we introduce two nodes u? and u+ in G?. The edges of G? and their capacities are defined as follows. For each edge (u, v) in G we add an edge (u+, v?) in G? with capacity?. For each node u in G we add the edge (u?, u+) with capacity c(u). Now it is easy to argue that any flow in G? corresponds to a flow in G and further all node capacities are satisfied.In place of ? one can use a value 1 +?v c(v).To obtain a max flow - mincut theorem we first define ans –t node cut as set of nodes V??V?{s, t}whose removal disconnects s from t.For a node-cut V? its capacity is ?u?V? c(u).The max-flow-mincut theorem for node capacities is:The maximums?t node- capacitied flow in Gis equal to the minimum capacity of ans ?t node-cut in G. This follows by applying the standard maxflow-mincut theorem to G?as constructed above.Given a graph G with node capacities we reduce the problem to one with edge capacities in a new graph G? as follows. For each node u in G we introduce two nodes u? and u+ in G?. The edges of G? and their capacities are defined as follows. For each edge (u, v) in G we add an edge (u+, v?) in G? with capacity?. For each node u in G we add the edge (u?, u+) with capacity c(u). Now it is easy to argue that any flow in G? corresponds to a flow in G and further all node capacities are satisfied.In place of ? one can use a value 1 +?v c(v).To obtain a max flow - mincut theorem we first define ans –t node cut as set of nodes V??V?{s, t}whose removal disconnects s from t.For a node-cut V? its capacity is ?u?V? c(u).The max-flow-mincut theorem for node capacities is:The maximums?t node- capacitied flow in Gis equal to the minimum capacity of ans ?t node-cut in G. This follows by applying the standard maxflow-mincut theorem to G?as constructed above.