Time complexity of the Ford-Fulkerson method in a flow network with unit capacity edges

Question

Will the Ford-Fulkerson algorithm find a maximum flow of a unit-capacity flow network (all edges have unit capacity) with n vertices and m edges in O(mn) time?

Hardener

Answer 1

O(M*f) is a known running time estimation for Ford-Fulkerson on graphs with integer capacities, where M is the number of edges and f the value of maximal flow, just because it is easy to find augmenting paths in O(M) each, and each such path increases the flow by at least 1.

If your graph has no duplicate edges (that is, there is no pair of edges that has the same start and end vertices), and each edge has unit capacity, then the the maximal flow f is no more than the number of vertices N (just because there is no more than N-1 edges going from the source), and therefore the complexity is indeed O(N*M).

However, if your graph is allowed to have duplicate edges (but still each edge has capacity of 1), then f can be bigger than N, and up to M, and the time complexity can become O(M*M), and it is not difficult to come with an example where such complexity takes place.

Staminody