= Uniform capacity perturbation of a flow network
{title2=$v(\varepsilon)=\min_S(c(S)+\varepsilon m(S))$}
= Uniform capacity perturbations of a flow network
{synonym}
If every directed edge capacity increases by $\varepsilon$, a <cut of a flow network> with $m(S)$ outgoing edges gains $\varepsilon m(S)$. By the <max-flow min-cut theorem>, the new <maximum flow> value is
$$
v(\varepsilon)=\min_{S:s\in S,\,t\notin S}\bigl(c(S)+\varepsilon m(S)\bigr).
$$
For a finite <flow network>, this is a nondecreasing concave piecewise-linear function, and its active cut can change as $\varepsilon$ varies. Two unit-capacity edge-disjoint two-edge source-to-sink paths gain $2\varepsilon$, refuting an invariably exact $\varepsilon$ increase. If there is a directed source-to-sink path, every cut has at least one outgoing edge and the increase is at least $\varepsilon$; without a path it can be zero.
Back to article page
