0
$\begingroup$

I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead of DFS) variant of Ford-Fulkerson algorithm.

The point is on time complexity, Ford-Fulkerson algorithm has $O(|E||f_{max}|)$ whereas Edmonds-Karp is presented to run in $O(|V||E|^2)$. My main is question is then, how can I decide which of these algorithm is the faster on an arbitrary max-flow problem ?

I feel very unconfortable with the $f_{max}$ even if I understand it, because determining it is the goal of the algorithm so estimating it is likely to be hard on the very general case. Depending on problem, $f_{max}$ may be very high with respect to $|E|$, even if one can possibly apply a scale factor on all edges.

I also do not understand where the runtime difference comes from. Generally BFS and DFS have the same expected runtime, the difference between them is more on problem dependant space requirement and features like shortest path, topological order...

$\endgroup$
  • $\begingroup$ In a world where parallel computers are ubiquitous, it would not be unthinkable to run both algorithms in parallel and take the answer of the one which answers first. $\endgroup$ – dkaeae May 9 at 15:12
  • $\begingroup$ @dkaeae: You can even do this on a single CPU: run a step of one, then a step of the other. My guess is that it's not done because it's empirically rare for a DFS-based FF to be materially faster than EK, and in the cases where it's not, you (at best) double the time to find a solution. $\endgroup$ – j_random_hacker May 9 at 17:03
3
$\begingroup$

Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former. In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other variant of FF in preference to EK).

The above does not imply that EK is faster than a particular (say, DFS-based) variant of FF on any particular instance.

BFS and DFS have the same runtime, but DFS only promises to find a path from source to sink in the residual graph -- not necessarily a shortest possible such path, which BFS does promise. It's possible to show that no modification to the residual graph ever reduces the distance from the source to any vertex; with this, and the fact that BFS always finds a shortest path, it's possible to show that after finding at most $|V||E|$ augmenting paths, no source-to-sink path remains in the residual graph. This page gives a full proof -- I've only skimmed it, but note that when it says that "That is, [the distance from the source to all other nodes] is always increasing", it in fact means (or should mean) that this never decreases -- that is, the distance from the source to a particular node can stay the same after an augmentation, or it can be larger, but it can never be smaller.

$\endgroup$
  • $\begingroup$ A complete answer, thank you. So is there any reason to use Ford-Fulkerson instead of Edmonds-Karp (not considering coding difficulty). $\endgroup$ – Vince May 9 at 18:17
  • $\begingroup$ You're welcome :) But I remind you that the question you just asked is similar to "Is there any reason to paint my house instead of painting my house red?" EK is FF, with some details that are left out of FF filled in (specifically: how to choose the next augmenting path). Is there a reason to use a non-BFS-based variant of FF, such as a DFS-based variant? I don't know of one, but I'm not an expert. There are other, non-FF algorithms for solving maximum flow, some of which have better guarantees. $\endgroup$ – j_random_hacker May 9 at 19:27

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.