Thursday, September 13, 2012

Max Flow

A couple of weeks ago Suresh tweeted the following result of James Orlin
I'm thinking, wow, max flow is one of the major standard algorithms problems, and O(nm)  time (n = number of vertices, m = number of edges) seems like a great clean bound. But there hasn't been much chatter about this result beyond Suresh's tweet.

Reading Orlin's paper gives some clues. The previous best bound due to King, Rao and Tarjan has a running time of O(nm logm/(n log n)n) = O(nm log n) just a logarithm off from O(nm). Orlin doesn't directly give an O(nm) algorithm, his takes time O(nm+m31/16log2n). It's the minimum of the running times of King-Rao-Tarjan and Orlin's algorithms that yields O(nm). Nor is O(nm) tight, Orlin also gives an algorithm with a running time of O(n2/log n) when m=O(n).

I don't mean to knock Orlin's work, he makes real progress on a classical algorithmic problem. But somehow I think of O(nm) as a magical bound when it is really just another bound. I'm just fooled by simplicity.


  1. it is really just another bound — Unlike a 0.001 reduction in the matrix multiplication exponent?

  2. I mentioned it on my blog after Suresh's tweet.

    I echo what I'm taking to be Jeff's confusion by your statements. There may be many reasons to like, or not like, Orlin's resut or Vassilevska Williams' matrix multiplication result. Both are improvements on long-standing results to very important problems, but the "gap" in your reaction to the two results isn't clear, and perhaps merits further explanation (if you feel like writing more about it).

  3. Funnily enough, Jim Orlin's contribution relies on Williams' "breakthrough" on fast matrix multiplication.

    1. This is clearly not true: even a cursory reading of the paper shows that the O(nm) result is not based in any way on fast matrix multiplication, much less on status of known bounds on ω.

    2. @circle: Well, Orlin doesn't use fast matrix multiplication to derive the O(mn) bound... admitted. But when analysing further possible improvements (the "or better" part of the paper), he does. ("relies on Williams' breakthrough" still may be a bit too provactive, though ...admitted, again.)

  4. That O(nm) is a nice function IS important since
    (and this is not rigorous) it could be tight, where as
    something like O(nlog_{n/m} m) is not.

    Just speaking for me
    Matrix Mult impressed me since it was open so long with very little progress.

    Max Flow impresses me since O(nm) is a nice function.

    (Perhaps I am easy to impress.)

  5. Evaluating the quality of papers is pretty hard for anyone who is not an expert on the particular topic. Conferences program committees have 3 reviewers, discussion, etc.. and still get it wrong sometime.

    So, the amount of blog chatter, or "simplicity" of the bound are not really markers of quality. There can be a paper that "merely" shaves a log factor, but crosses an important barrier and introduces new ideas.

    I am no max-flow expert so will not claim I can evaluate this work, but it seems the experts considered O(nm) to be the "right" bound for general max-cut without any constraints on the capacities (though it can be significantly improved when the ratio of capacities is at most polynomial, and perhaps the results of this paper for m=O(n) and prior works for m=Omega(n^2) show that you could shave another log n factor?). To quote the JACM 1998 paper of Goldberg and Rao: (which achieves O*(n^{2/3}m) for polynomial capacity ratio)

    "The Omega(nm) bound is a natural barrier for maximum flow algorithms. In a path decomposition of a flow, the total path length is Theta(nm) in the worst case. This implies an Omega(nm) lower bound on algorithms which output explicit flow decomposition and on algorithms which augment flow one path at a time and, for each augmenting path, one arc at a time. This lower bound does not apply to algorithms that work with preflows or use data structures like dynamic trees [Sleator and Tarjan 1983] to manipulate flows. However, in spite of numerous attempts, no previous algorithm achieves this lower bound in general."

    Boaz Barak