22
$\begingroup$

This question is about the time complexity of the Ford-Fulkerson maximum flow algorithm when using DFS to find augmenting paths.

There is a well-known example showing that using DFS one can need a linear number of iterations in the maximum flow, see for instance the Wikipedia page linked to above.

However, I'm not really convinced by this example: a standard DFS implementation would not exhibit the behaviour of alternating between B and C as first node of the path (using the vertex names from the Wikipedia page).

So, let us impose the very natural condition that whenever the DFS visits a node $u$, it always examines the neighbors of $u$ in the same order. Are there still examples for which FF with DFS uses a large number of iterations?

As a variant, suppose that we have the additional property that the different orderings of neighbors are consistent with some arbitrary but fixed global ordering of the vertices. Does that make a difference?

This seems to me like a pretty basic question; I apologize in advance if the answer is well-known but I am not an expert on flows and some googling did not turn up anything.

Edit: The answer turns out to be yes, there are still examples. See Figure 2 of this paper. In these examples FF with DFS take an exponential (in the number of vertices) number of iterations. It seems easy to prove that this is tight, i.e., that the number of iterations are always bounded by $2^{O(n)}$ (regardless of the values of the capacities).

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ I have wondered about the same question. $\endgroup$
    – Luca Trevisan
    Feb 24, 2011 at 1:45
  • 1
    $\begingroup$ (1) Nice question. (2) I think that the bad-case example (like the one in Wikipedia) is usually introduced as a reason why some consideration about visiting order is necessary, not as a reason against using depth-first search. $\endgroup$
    – Tsuyoshi Ito
    Feb 24, 2011 at 14:57
  • 6
    $\begingroup$ I don't think I can now teach FF without an answer to this question. Nice !! $\endgroup$
    – Suresh Venkat
    Feb 24, 2011 at 16:52
  • $\begingroup$ Isn't finding the maximum flow in a minimal number of iterations NP-Complete? $\endgroup$
    – user834
    Feb 24, 2011 at 19:20

1 Answer 1

Reset to default
13
$\begingroup$

If adjacency lists are fixed in advance then DFS always terminates (even if there are irrational capacities).

See Dean, Goemans, Immorlica -- Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.

Improve this answer
$\endgroup$
1
  • 11
    $\begingroup$ Thanks. That does not in itself answer my question, however, the example given in Figure 2 of the Dean-Goemans-Immorlica paper shows a recursive construction based on the standard example, which does answer my question and shows that FF with DFS can require exponentially many iterations. $\endgroup$
    – Per Austrin
    Feb 24, 2011 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.