3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ "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$. $\endgroup$
    – David Richerby
    May 21, 2015 at 23:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.