# Max Flow / Linear Programming Reduction Variant

While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause:

Here are two variants of the standard Maximum Flow problem. Show that both of them can be solved efficiently by reducing each to linear programming. (Note: (1) and (2) are separate problems)

(1) Each directed edge has, in addition to its capacity, a nonnegative lower bound on the flow that it has to carry.

(2) The total outgoing flow from each node $v$ (excluding the source node and sink node), does not equal the total incoming flow, but is smaller by a factor of $(1 - \epsilon_v)$, where $\epsilon_v$ stands for a loss coefficient associated with node $v$.

My initial thoughts on each are as follows: (1) Aside from the constraints for the standard Max Flow problem, add the following constraint for each edge $e$: $0 \leq l_e \leq f_e \leq c_e$ (where $l_e$ stands for the lower bound on the flow). Is this all the modification that is necessary for a reduction?

(2) For every vertex $v$ except the source and sink vertices: $($sum of flow into $v)=($sum of flow out of $v - (1-\epsilon_v))$, where $0 \leq \epsilon_v \leq 1$. I figured that since the problem states the sum of outward flow must be smaller than incoming flow by some factor, epsilon must be nonnegative and at most 1. Am I missing something?

• (1) That's it (2) if you meant factor, then $\sum \texttt{out} \leq (1-\epsilon_v)\sum \texttt{in}$. – G. Bach Mar 30 '16 at 15:11
• Thanks! Misinterpreted the phrase "by a factor". But then wouldn't the constraint simply be $\sum out = (1-\epsilon_v) \sum in$? – user3280193 Mar 30 '16 at 20:34
• If the out-sum is supposed to be exactly that fraction of the in-sum, then yes; if it's supposed to be at most that fraction, then the inequality is the right constraint. – G. Bach Mar 30 '16 at 21:35