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?