My intuition says it would simply be the number of edges leaving s.
I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow exists.

This variation simplifies the running time because for any augmenting path, we can add the same amount of positive flow which is equal to any original edge capacity. So no edge leaving s would get used twice and the runtime is simply how many edges leave s.

I think that makes sense, but maybe I'm missing something...

  • $\begingroup$ If you're not sure whether your ideas are correct, try expressing them more formally. $\endgroup$ Nov 19 '17 at 16:42
  • $\begingroup$ You may as well treat all edges as having capacity $1$. On each iteration of Ford-Fulkerson, the flow must increase by at least $1$ unit. But, finding an augmenting path on each iteration still takes time. Does this help? $\endgroup$
    – Joppy
    Nov 20 '17 at 10:17
  • $\begingroup$ @Joppy is the number of edges leaving s O(M)? And then for each of these edges I'd have the nested complexity of finding an augmenting path? $\endgroup$ Nov 20 '17 at 15:42

Your Answer

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

Browse other questions tagged or ask your own question.