In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{min}$.

I need to be sure that the minimum flow satisfies not only all the upper bounds (capacities), but also all the lower bounds.

Is it even possible? And if yes, which changes do I need to make to my flow network so that the max flow algorithm takes these lower bounds into account?


Yes, it is possible to solve such problems efficiently. The minimum-cost circulation problem is a generalization of the standard network flow problem, which allows you to set both lower bounds and upper bounds on the flow through each edge. (You can set all costs equal to 1.) There are polynomial-time algorithms to solve instances of the minimum-cost circulation problem.

I don't know if there's a simple way to do with a standard algorithm for network flow.

  • $\begingroup$ I am just a bit afraid about the complexity, since min-cost max flow's complexity includes the value of the total flow (if I am not mistaken), while push-relabel for max flow just runs O(n^3) in the number of nodes. However, I found this paper: pdfs.semanticscholar.org/03a2/…. Do you think this might work? $\endgroup$ – karlosss Nov 9 at 12:46
  • $\begingroup$ @karlosss, ahh, yes, that's very nice. Would you like to write up an answer summarizing that approach? That's a much better solution than my answer. Good stuff, I enjoyed learning about that! $\endgroup$ – D.W. Nov 10 at 2:53
  • $\begingroup$ I kindof already went through it and I THINK that I got it, but if you summarize it "for dummies", you will definitely deserve an upvote and accepted answer :) $\endgroup$ – karlosss Nov 10 at 12:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.