Ford-Fulkerson Running Time

Question

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!

In the analysis of Ford-Fulkerson I understand why the while loop runs no more than $val(f^*)$ times but I don't see why it only takes $O(E)$ time to find an augmenting path. Using a BFS or DFS would give $O(V+E)$ no? The running time I see everywhere says $O(E\cdot val(f^*))$

Also, given $C$, the maximum capacity of any edge in the network, I see a lot of people stating the bound $val(f^*)\leq nC$ where $n$ seems to be $|V|$. However it isn't clear why this relation holds. $val(f^*)\leq C|E|$ makes more sense to me but never seems to be used...

Answer 1

There might be some more clever trick in the analysis to get rid of the $V$, but at the very least, I can provide some intuition as to why you can get rid of it.

With Ford-Fulkerson, it is generally assumed that you are working with connected graphs.

For any connected graph with $V$ nodes, there are at least $V-1$ edges, since each node needs at least one edge (except the "last" one in a sense) to be connected.

This means that, either there are $O(V)$ edges, in which case $O(V + E) = O(E)$, or the number of edges dominates the number of vertices (for example, when there are $O(V^2)$ edges), in which case the $V$ gets dominated and we can just write $O(E)$.

When you learn breadth-first search and depth-first search, one of the main applications is testing for connectedness and finding connected components. Here, you could be dealing with a graph with thousands of components, so it makes sense to not assume that there is one component.