patternMinor
Ford-Fulkerson Running Time
Viewed 0 times
runningfulkersonfordtime
Problem
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...
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...
Solution
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.
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.
Context
StackExchange Computer Science Q#42910, answer score: 5
Revisions (0)
No revisions yet.