## 1. Goal

Our 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 Problem

The 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 Algorithm

Our 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.

See
```"Faster and More Dynamic Maximum Flow
Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli,
Robert E. Tarjan, and Renato F. Werneck
```
which will appear in ALGO ESA 2015.
```"Maximum Flows By Incremental Breadth-First Search"