Guest Blog by Andrew Goldberg on the recent Max Flow in O(nm) time algorithm.
Maximum Flow in O(nm) Time
Recently, Jim Orlin published an
O(nm) maximum flow algorithm. This solves a long-open problem. In this blog entry, we assume that the reader is familiar with the maximum flow problem, which is a classical combinatorial optimization problem with numerous applications. (If not then see the
Wikipedia entry here.)
Let n and m denote the number of vertices and arcs in the input graph, respectively, and if the input capacities are integral, U denotes the value of the biggest one. Running time of a strongly polynomial algorithm is a polynomial function of n and m; the time of a polynomial algorithm may depend on log(U) as well.
Maximum flow algorithms have been studied since 1950's with the first strongly polynomial-time algorithm developed in 1972 by
Edmonds and Karp. This was followed by faster and faster algorithms. In 1980, Galil and Namaad developed an O(nm log
2n) algorithm, coming close to the nm bound. The latter bound is a natural target for a maximum flow algorithm because a flow decomposition size is THETA(nm). In 1983,
Sleator and Tarjan developed the dynamic tree data structure to improve the bound to O(nm log(n)); in 1986, Goldberg and Tarjan developed the push-relabel method to get an O(nm log(n
2/m)) bound. The race towards O(nm) continued, with improvements being made every few years, until
King, Rao and Tarjan developed O(nm + n
2+ε) and O(nm log
m/(n log(n) n) algorithms in 1992 (SODA) and 1994 (Journal of algorithms-the paper pointed to), respectively. These bounds match O(nm) except for sparse graphs.
No better strongly polynomial algorithm for sparse graphs has been developed for 18 years, until Orlin's recent result. Orlin not only gets the O(nm) bound, but also an O(n
2/log(n)) bound for very sparse graphs with m = O(n). His result is deep and sophisticated. It uses not only some of the most powerful ideas behind the efficient maximum and minimum-cost flow algorithms, but a dynamic transitive closure algorithm of Italiano as well. Orlin closes the O(nm) maximum flow algorithm problem which has been open for 32 years.
Sometimes solving an old problem opens a new one, and this is the case for the maximum flows. The solution to the maximum flow problem is a flow, and flows have linear size, even when they have decompositions of size THETHA(nm). For the unit-capacity problem, an O(min(n
2/3, m
1/2) m) algorithm has been developed by Karzaov (and independently by
Even and Tarjan) in the early 1970's. This bound is polynomially better than nm. In 1997, Goldberg and Rao developed a weakly polynomial algorithm that comes within a factor of O(log(U) log
n2/m n) of the unit flow bound, and Orlin's algorithm uses this result. A natural question to ask at this point is whether there is an O(nm/n
ε) maximum flow algorithm for some constant epsilon.
