# Maximum Flow with Binary Capacities

Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow can be found?

It seems that the Dinic Algorithm will accomplish this $O \left( m n^{2/3} \right)$ where $n$ is the number of nodes and $m$ is the number of vertices. From table 1 in this paper, it seems reasonable to guess this was still the state of the art in 2001. Is this the best that is currently known?

• "Constant capacity" would be a more natural phrasing than "binary capacity" since what you really mean is that all edges have the same capacity $c$ and all non-edges have capacity zero. WLOG, we may as well take $c=1$. – David Richerby May 21 '15 at 23:20

According to Goldberg's post on the Fortnow–Gasarch blog from 2012, the best algorithm for unit capacity networks is the Karzaon/Dinic/Even–Tarjan algorithm, which runs in time $O(\min(n^{2/3},m^{1/2})m)$ time. The post came after Orlin's $O(nm)$ algorithm. Goldberg and Rao extended this result to any constant capacity (their running time is linear in the logarithm of the maximal capacity).
There is a more recent line of work which gives an approximation to the maximum flow in time $O(m^{1+o(1)})$, but this doesn't make use of any bound on the capacities.