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. 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 separation of the nodes into two sets S and T with s in S, t in T such that we get a minimal cut:
Minimize ∑v in S, w in T capacity(v,w)The Minimum s-t Cut Problem is the motivating problem for many of the applications of 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.
"Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search" Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert E. Tarjan, and Renato F. Werneckwhich will appear in ALGO ESA 2015.
"Maximum Flows By Incremental Breadth-First Search" A.V. Goldberg, S.Hed, H. Kaplan, R.E. Tarjan, and R.F. Werneckwhich appeared in ALGO ESA 2011 (ESA 2011 presentation slides).
(Check 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