Maximum flow problem with both minimum and maximum capacities

Question

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.

Answer 1

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).

Answer 2

Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t\,s}$.

There are many Min Cost Flow algorithms, see this link for example.