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?

  • $\begingroup$ (1) That's it (2) if you meant factor, then $ \sum \texttt{out} \leq (1-\epsilon_v)\sum \texttt{in}$. $\endgroup$ – G. Bach Mar 30 '16 at 15:11
  • $\begingroup$ Thanks! Misinterpreted the phrase "by a factor". But then wouldn't the constraint simply be $\sum out = (1-\epsilon_v) \sum in$? $\endgroup$ – user3280193 Mar 30 '16 at 20:34
  • $\begingroup$ 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. $\endgroup$ – G. Bach Mar 30 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.