I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow -

1) We need to assign a large capacity to all edges and find flow f
2) Construct G $_{1}$ where all edges are reversed and each edge has capacity f$_{e}$ - l$_{e}$
3) We need to then find the max flow from t to s in G$_{1}$ that is f$_{1}$
4) Then, the minimum flow in G is f-f$_{1}$

My question is- Why can't we find a s to t path in G with the least value of l$_{e}$. The least value of l$_{e}$ would be the minimum flow that could be pushed through the network?


Imagine you have the following graph (in red are the minimum capacities):

enter image description here

The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.

| cite | improve this answer | |

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.