Exercise $7\mathrm{.}13,$ Page $420.$ 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 the variant of the Maximum$-$Flow and MinimumCut problems with node capacities.

$2$

Let $G=(V,E)$ be a directed graph, with source $sinV,sinktinV,$ and non$-$negative node capacities $\{c_{v}0\}$ for each vinV. Given a flow $f$ in this graph, the flow through a node $v$ is defined as $f^{in}(v).$ We say that a flow is feasible if it satisfies the usual flow$-$conservation constraints and the node$-$capacity constraints: $f^{in}(v)c_v$ 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.