<p>I am one of the authors of the paper linked above. </p>

<p>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. </p>

<p>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. </p>

<p>Finally, in case anyone is interested, the data from our experiments is available here:
<a href="http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html">http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html</a></p>

<p>The code will also soon be available too. </p>

CC BY-SA 3.0
2013-03-19T04:26:57.490Z
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
CC BY-SA 3.0
2013-03-17T22:44:06.453Z
2013-03-17T22:44:06.453Z
Dhruv Batra
<p>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.**</p>

<p>a good strategy <em>for practical purposes</em> 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. </p>

<p>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.</p>

<p>[1] <a href="http://ttic.uchicago.edu/~dbatra/publications/assets/vb_bmvc12.pdf">MaxFlow Revisited:
An Empirical Comparison of Maxflow
Algorithms for Dense Vision Problems</a> by Verma and Batra, 2012</p>

<p>** 
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 <a href="http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/">blogs</a>. </p>

<p>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").</p>

CC BY-SA 3.0
2013-02-04T21:13:39.120Z
+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
CC BY-SA 3.0
2013-02-04T22:07:34.483Z
Robert Sedgewick said in [a fairly recent talk](http://www.cs.princeton.edu/~rs/talks/PathsInGraphs07.pdf) 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
CC BY-SA 3.0
2013-02-05T02:58:05.237Z
@Rob, the only relevant part in this answer is a link to the paper and there isn't much in the answer explaining why that paper is linked at all. I would guess that the OP found the link by Google and hasn't read it. The rest of the answer is some general remarks and commentary stating OP's personal perspective on issues that he is not an expert on and not really relevant here. Answers are not blog posts. A link to a relevant paper might be good as a comment but it doesn't make an answer. This is a  bad answer if it is one. That is why I have down voted it.
Kaveh
CC BY-SA 3.0
2013-02-05T03:58:43.600Z
@Kaveh fair enough. I found the paper to be a useful indicator of what people consider to be practically useful algorithms.  I agree that much is left unanswered.
Rob Lachlan
CC BY-SA 3.0
2013-02-05T15:42:07.290Z
cannot write a treatise on the subj. skimmed paper, its highly relevant. esp given that authors attempt to test all recent state-of-the-art algorithms & hard instances in one field/domain may tend to coincide with hard ones in another. ie performance results can generally/often carry between domains. empirical testing is highly relevant with basic disclaimers. TCS ivory tower crowd devalues empirical approaches & can get lost in theory as sedgewick points out. even Fortnow & Lipton, premiere TCS authorities, while crediting advances, still question "galactic" algorithms. the paper is _science_
vzn
CC BY-SA 3.0
2013-02-05T18:09:35.427Z
I don't understand the downvotes either. There's no reason to believe that the poster did NOT read the linked article, and it does appear to be relevant. I can see the desire not to upvote, but not a downvote.
Suresh Venkat
CC BY-SA 3.0
2013-02-06T04:57:22.403Z
@Suresh, my down-vote was not for that reason. As I explained above I see this as a one-line link answer which AFAIK is not considered a good answer (plus some general commentary expressing personal perspective which I think belong to a blog post and not here). I would take back my down-vote if the answer is edited, the general commentary is removed, and the relevance of this particular article to this particular question is explained.
Kaveh
CC BY-SA 3.0
2013-02-04T19:48:59.810Z
2013-02-04T20:08:12.190Z
2013-02-04T20:08:12.190Z
vzn
<p>You might be interested in
<strong><em>Maximum Flows by Incremental Breadth-First Search</em></strong>
by Goldberg, Hed, Kaplan, Tarjan, and Werneck</p>

<p><a href="http://research.microsoft.com/pubs/150437/ibfs-proc.pdf" rel="noreferrer">http://research.microsoft.com/pubs/150437/ibfs-proc.pdf</a>
<a href="http://www.cs.tau.ac.il/~sagihed/ibfs/" rel="noreferrer">http://www.cs.tau.ac.il/~sagihed/ibfs/</a></p>

CC BY-SA 3.0
2014-09-02T03:59:30.540Z
2014-09-02T03:59:30.540Z
Christian Sommer
<p>For the <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem" rel="noreferrer">maximum flow problem</a>, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year.  Orlin's <a href="http://jorlin.scripts.mit.edu/docs/papersfolder/O%28nm%29MaxFlow.pdf" rel="noreferrer">Max flows in O(mn) time or better</a> gives an algorithm that runs in O(VE).</p>

<p>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):</p>

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

<p>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?</p>

<p>Note: this question was originally asked on stack overflow, <a href="https://stackoverflow.com/questions/14667586/are-any-of-the-state-of-the-art-maximum-flow-algorithms-practical">here</a>, but I was told it would be a better fit here.</p>

<p><strong>EDIT</strong>: I asked <a href="https://cs.stackexchange.com/questions/9501/are-link-cut-trees-ever-used-in-practice-for-max-flow-computation-or-other-appl">a related question on cs.stackexchange</a>, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.</p>

CC BY-SA 3.0
2013-02-04T06:36:38.003Z
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
CC BY-SA 3.0
2013-02-04T06:39:02.793Z
@vzn I would expect that some big tech companies would be willing to put in the effort to see if these algorithms are worth the improvement, no? (I'm not sure how often max-flow problems come up in such places...I'd assume somewhat often.)
usul
CC BY-SA 3.0
2013-02-04T06:45:41.583Z
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
CC BY-SA 3.0
2013-02-04T08:20:58.870Z
@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
CC BY-SA 3.0
2013-02-04T14:40:46.813Z
_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ε
CC BY-SA 3.0
2013-02-04T18:45:03.793Z
looking at the paper, it does seem to verge on "not likely to be actually implemented due to a high threshhold of logical complexity" see eg [Powerful Algorithms too complex to implement](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement). some commentary/comments on the orlin result by lance fortnow et al [on his blog](http://blog.computationalcomplexity.org/2012/09/max-flow.html). the lower bound utilizes also the King, Rao and Tarjan algorithm so both algorithms would have to be implemented to get the theoretical optimum.
vzn
CC BY-SA 3.0
2013-02-04T18:59:00.970Z
as for companies implementing new max flow algorithms, that is possible, but then why release them to the public domain & other parties when they invested the time? sometimes better for them to retain the competitive advantage. this is heightened in that, in fact, have heard max flow is useful in realtime trading applications where secrecy is common!
vzn
CC BY-SA 3.0
2013-02-05T12:39:05.583Z
@vzn I am not very familiar with article licenses, but shouldn't they reference the author in the software and if possible, notify him as well. I am thinking a copyleft license would be appropriate here. Perhaps this would make a good question.
chazisop
CC BY-SA 3.0
2013-04-20T18:36:06.727Z
[Here's the code](http://www.columbia.edu/~cs2035/code.html) from [Experimental study of minimum cut algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.414&rep=rep1&type=pdf).
Austin Buchanan
CC BY-SA 3.0
2014-09-02T04:32:01.933Z
seems relevant: http://cacm.acm.org/magazines/2014/8/177011-efficient-maximum-flow-algorithms/fulltext
Radu GRIGore
<ds.algorithms><graph-algorithms><application-of-theory><max-flow>
Are any of the state of the art Maximum Flow algorithms practical?
Rob Lachlan
# Are any of the state of the art Maximum Flow algorithms practical?

(Asked by: username_0 on 2013-02-03)

For the [maximum flow problem](http://en.wikipedia.org/wiki/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](http://jorlin.scripts.mit.edu/docs/papersfolder/O%28nm%29MaxFlow.pdf) 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](https://stackoverflow.com/questions/14667586/are-any-of-the-state-of-the-art-maximum-flow-algorithms-practical), but I was told it would be a better fit here.

**EDIT**: I asked [a related question on cs.stackexchange](https://cs.stackexchange.com/questions/9501/are-link-cut-trees-ever-used-in-practice-for-max-flow-computation-or-other-appl), specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.

**Tags:** ds.algorithms, graph-algorithms, application-of-theory, max-flow

> **Comments:**
> **username_1**: 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...  
> **username_2**: @username_1 I would expect that some big tech companies would be willing to put in the effort to see if these algorithms are worth the improvement, no? (I'm not sure how often max-flow problems come up in such places...I'd assume somewhat often.)  
> **username_3**: 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.  
> **username_0**: @username_1 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.  
> **username_4**: _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.  
> **username_1**: looking at the paper, it does seem to verge on "not likely to be actually implemented due to a high threshhold of logical complexity" see eg [Powerful Algorithms too complex to implement](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement). some commentary/comments on the orlin result by lance fortnow et al [on his blog](http://blog.computationalcomplexity.org/2012/09/max-flow.html). the lower bound utilizes also the King, Rao and Tarjan algorithm so both algorithms would have to be implemented to get the theoretical optimum.  
> **username_1**: as for companies implementing new max flow algorithms, that is possible, but then why release them to the public domain & other parties when they invested the time? sometimes better for them to retain the competitive advantage. this is heightened in that, in fact, have heard max flow is useful in realtime trading applications where secrecy is common!  
> **username_5**: @username_1 I am not very familiar with article licenses, but shouldn't they reference the author in the software and if possible, notify him as well. I am thinking a copyleft license would be appropriate here. Perhaps this would make a good question.  
> **username_6**: [Here's the code](http://www.columbia.edu/~cs2035/code.html) from [Experimental study of minimum cut algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.414&rep=rep1&type=pdf).  
> **username_7**: seems relevant: http://cacm.acm.org/magazines/2014/8/177011-efficient-maximum-flow-algorithms/fulltext  

---

## 3 answers

### Answer by username_8 on 2013-03-17. Score: 23

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.

> **Comments:**
> **username_1**: 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!  

---

### Answer by username_1 on 2013-02-04. Score: 8

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](http://ttic.uchicago.edu/~dbatra/publications/assets/vb_bmvc12.pdf) 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](http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/).

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").

> **Comments:**
> **username_0**: +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.  
> **username_9**: Robert Sedgewick said in [a fairly recent talk](http://www.cs.princeton.edu/~rs/talks/PathsInGraphs07.pdf) 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.  
> **username_10**: @Rob, the only relevant part in this answer is a link to the paper and there isn't much in the answer explaining why that paper is linked at all. I would guess that the OP found the link by Google and hasn't read it. The rest of the answer is some general remarks and commentary stating OP's personal perspective on issues that he is not an expert on and not really relevant here. Answers are not blog posts. A link to a relevant paper might be good as a comment but it doesn't make an answer. This is a  bad answer if it is one. That is why I have down voted it.  
> **username_0**: @username_10 fair enough. I found the paper to be a useful indicator of what people consider to be practically useful algorithms.  I agree that much is left unanswered.  
> **username_1**: cannot write a treatise on the subj. skimmed paper, its highly relevant. esp given that authors attempt to test all recent state-of-the-art algorithms & hard instances in one field/domain may tend to coincide with hard ones in another. ie performance results can generally/often carry between domains. empirical testing is highly relevant with basic disclaimers. TCS ivory tower crowd devalues empirical approaches & can get lost in theory as sedgewick points out. even Fortnow & Lipton, premiere TCS authorities, while crediting advances, still question "galactic" algorithms. the paper is _science_  
> **username_3**: I don't understand the downvotes either. There's no reason to believe that the poster did NOT read the linked article, and it does appear to be relevant. I can see the desire not to upvote, but not a downvote.  
> **username_10**: @Suresh, my down-vote was not for that reason. As I explained above I see this as a one-line link answer which AFAIK is not considered a good answer (plus some general commentary expressing personal perspective which I think belong to a blog post and not here). I would take back my down-vote if the answer is edited, the general commentary is removed, and the relevance of this particular article to this particular question is explained.  

---

### Answer by username_11 on 2014-09-02. Score: 5

You might be interested in
***Maximum Flows by Incremental Breadth-First Search***
by Goldberg, Hed, Kaplan, Tarjan, and Werneck

<http://research.microsoft.com/pubs/150437/ibfs-proc.pdf>
<http://www.cs.tau.ac.il/~sagihed/ibfs/>


---

