of the Maximum flow problem, which can be solved in time. Hence the complexity of the simple algorithm described above is in total.

An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v variesover all vertices. This reduces the complexity to and is sound since, if a cut of capacity less than k exists,it is bound to separate u from some other vertex. It can be further improved by an algorithm of Gabow