# Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE).

On the other hand, the algorithms I most commonly see implemented are (I don't claim to have done an exhaustive search; this is just from casual observation):

• Edmonds-Karp: $O(VE^2)$,
• Push-relabel: $O(V^2 E)$ or $O(V^3)$ using FIFO vertex selection,
• Dinic's Algorithm: $O(V^2 E)$.

Are the algorithms with better asymptotic running time just not practical for the problem sizes in the real world? Also, I see "Dynamic Trees" are involved in quite a few algorithms; are these ever used in practice?

Note: this question was originally asked on stack overflow, here, but I was told it would be a better fit here.

EDIT: I asked a related question on cs.stackexchange, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.

-
speaking in a general sense, whether an algorithm is "practical" vs whether it is "implemented" are a bit different. ideally authors would release implementations of their own algorithms in which case it would usually be "practical" to use them. unf this is often more the exception in TCS literature. but its often not "practical" to "implement" other authors algorithms only given descriptions in papers written in pseudocode, which are sometimes significantly or highly complex... successful implementation includes good testing for correctness, a sometimes daunting process... – vzn Feb 4 '13 at 6:36
Andrew Goldberg used to have a very nice code base for different variants of max flow based on his push relabel work. I've used the code in the past, and it was very clean. Unfortunately, the site appears to be defunct. – Suresh Venkat Feb 4 '13 at 6:45
@vzn I'm interested in whether the algorithms lend themselves to practical implementation at all. There are algorithms that don't, and some people have taken to calling these "galactic algorithms", because they have excellent asymptotic behaviour but so much overhead that there's currently no practical gain to implementing them. (Lower order terms matter, after all.) Matrix multiplication is the best example I can think of, where the asymptotically best solutions never see practical use. I'm curious as to whether Max flow is a similar situation. – Rob Lachlan Feb 4 '13 at 8:20
whether an algorithm is "practical" vs whether it is "implemented" are a bit different. — That is correct. An algorithm can be implemented without being practical, but not vice versa. – Jeffε Feb 4 '13 at 14:40
– Austin Buchanan Apr 20 '13 at 18:36

I am one of the authors of the paper linked above.

Just want to mention that we used state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision.

I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ones with poor theoretical guarantees. For instance, ref [5] from our paper (Boykov-Kolmogorov algorithm) is widely used in the computer vision community, but does not have a strongly polytime runtime bound.

Finally, in case anyone is interested, the data from our experiments is available here: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

The code will also soon be available too.

-
very neat that you joined the group! welcome! one question about the paper [since 1st finding it]. it would be very interesting to hear more about the process of selection of algorithms used in the paper— it didnt seem to fully elaborate on that. maybe you could share some "behind-the-scenes" background notes somewhere [eg web page?] about which algorithms were selected, which were omitted, why, what challenges there were in obtaining/running implementations, what you think of the more exotic algorithms such as Orlins recent one & their prospects for eventual implementation, etcetera! – vzn Mar 19 '13 at 4:26

there are several ways to answer this question but not necessarily a consensus answer. generally algorithms that have been implemented and released for public distribution are "practical". however, some algorithms that have been devised but not yet implemented may be practical but "the jury is out" on them so to speak.**

a good strategy for practical purposes is to look for a survey. also for those interested in practical algorithms, benchmarks against real world data can be an excellent guideline as to their expected "real world" behavior.

a benchmarking survey can be sufficient but will err on the side of viable algorithms. this is a recent, thorough empirical analysis of 14 "state-of-the-art" max flow algorithms benchmarked empirically versus vision processing instances, where max flow has many applications. "state of the art" is taken to refer to "implemented" algorithms.

[1] MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems by Verma and Batra, 2012

** some theoretical algorithms are in a category increasingly in the TCS community being informally referred to as "galactic" but unfortunately, TCS authors do not currently forthrightly self-label their algorithms in this category, and there is no published or generally accepted criteria for "galactic" algorithms, although there is reference in blogs.

practicality in this sense is possibly a new emerging dimension for theoretical study. ideally there would be a survey of max flow algorithms specifically on this "practical" axis/criteria, but likely that does not exist as of writing. its a more recently recognized/acknowledged concept in TCS that hasnt been thoroughly formalized yet (unlike eg the widespread acceptance of P algorithms as "efficient").

-
+1. I'm not sure why this was downvoted; I'm reading the paper that you linked to, and it has been very helpful in looking at what the practical approaches are, at least in that problem domain. – Rob Lachlan Feb 4 '13 at 21:13
Robert Sedgewick said in a fairly recent talk that the algorithm designer who does not run experiments risks becoming lost in abstraction. The talk is about finding paths in graphs, and is somewhat related to maxflow too. It doesn't answer the question, but might be interesting to someone. – Juho Feb 4 '13 at 22:07