1. GoalOur goal is to create the fastest and most robust Maximum Flow solver. We want to meet theory with practice: create an algorithm that is competitive in practice and with proven worst case time bounds.
2. The Maximum Flow ProblemThe Maximum Flow Problem is a fundamental problem in computer science with many real world applications such as network design and connectivity.
Given a network G=(V,E) with a positive capacity on every arc and two special nodes s and t, the task is to find a flow through the network that is feasible:
For every arc (v,w): 0 ≤ f(v,w) ≤ capacity(v,w) For every node v: ∑(w)f(v,w) = ∑(w)f(w,v)and maximal:
Maximize ∑(v)f(s,v) = ∑(v)f(v,t)The Minimum s-t Cut Problem is equivalent to the maximum flow problem and is the motivating problem for many of the application for maximum flow. In particular solving minimum s-t cut is an important tool in the field of computer vision, where it is mainly used for energy minimization problems such as image segmentation and stereo image processing. For more applications, see the Benchmark section.
3. The IBFS AlgorithmOur efforts created the Incremental Breadth First Search Algorithm or IBFS.
IBFS combines ideas from Boykov and Kolmogorov's algorithm (BK) with those from the shortest augmenting path algorithms and the push relabel algorithm. It is theoretically justified in the sense that it has a strongly polynomial worst case time bound of O(mn²). In addition, we showed that it performs better than BK on most applications we could find.
"Maximum Flows By Incremental Breadth-First Search A.V. Goldberg, S.Hed, H. Kaplan, R.E. Tarjan, and R.F. Werneck"which appeared in ALGO ESA 2011 (ESA presentation slides). Also see my MSC Thesis on IBFS and the thesis presentation slides.
We offer our code for free download, see the Code Section. Also see the Benchmark Section for a mapping of the current publicly available problem instances.
See the Maximum Flow Revisited page for another recent performance review of maximum flow algorithms. The review has found the IBFS algorithm to out perform other algorithm on applications previously believed to be best solved using the BK algorithm. Note the IBFS implementation (available in the Code Section) has been improved significantly since the above review. In particular, graph initialization time has dramatically decreased.
Another paper experimenting with IBFS is On Optimal Worst-Case Matching