I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$
A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow
However, I wasn't sure if this problem was exactly the same.
This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.
Thanks.
Best Answer
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) \ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).