# Running Time of Ford Fulkerson where all edges have equal capacity

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

• If you're not sure whether your ideas are correct, try expressing them more formally. – Yuval Filmus Nov 19 '17 at 16:42
• 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? – Joppy Nov 20 '17 at 10:17
• @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? – SleekPanther Nov 20 '17 at 15:42