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

<p>See <a href="http://www.cs.clemson.edu/~bcdean/paper15.html">Dean, Goemans, Immorlica -- Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data</a>.</p>

CC BY-SA 2.5
2011-02-24T19:20:49.913Z
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.
Per Austrin
CC BY-SA 2.5
2011-02-24T18:25:38.157Z
2011-02-24T18:25:38.157Z
ilyaraz
<p>This question is about the time complexity of the <a href="http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm">Ford-Fulkerson
maximum flow algorithm</a> when using DFS to find augmenting paths.</p>

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

<p>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).</p>

<p>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?</p>

<p>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?</p>

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

<p><strong>Edit:</strong>
The answer turns out to be yes, there are still examples.  See Figure 2 of <a href="http://www.cs.clemson.edu/~bcdean/iterm.pdf">this paper</a>.  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).</p>

CC BY-SA 2.5
2011-02-24T01:45:11.880Z
I have wondered about the same question.
Luca Trevisan
CC BY-SA 2.5
2011-02-24T14:57:07.647Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-24T16:52:59.637Z
I don't think I can now teach FF without an answer to this question. Nice !!
Suresh Venkat
CC BY-SA 2.5
2011-02-24T19:20:25.640Z
Isn't finding the maximum flow in a minimal number of iterations NP-Complete?
user834
<ds.algorithms><reference-request><max-flow>
Maximum flow using Ford-Fulkerson and DFS
Per Austrin
# Maximum flow using Ford-Fulkerson and DFS

(Asked by: username_0 on 2011-02-24)

This question is about the time complexity of the [Ford-Fulkerson
maximum flow algorithm](http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_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](http://www.cs.clemson.edu/~bcdean/iterm.pdf). 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).

**Tags:** ds.algorithms, reference-request, max-flow

> **Comments:**
> **username_1**: I have wondered about the same question.  
> **username_2**: (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.  
> **username_3**: I don't think I can now teach FF without an answer to this question. Nice !!  
> **username_4**: Isn't finding the maximum flow in a minimal number of iterations NP-Complete?  

---

## 1 answers

### Answer by username_5 on 2011-02-24. Score: 13 | Accepted answer

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](http://www.cs.clemson.edu/~bcdean/paper15.html).

> **Comments:**
> **username_0**: 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.  

---

