3
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 9, 2019 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. ♦
    Commented Nov 10, 2019 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
    Commented Nov 10, 2019 at 12:59

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