  We provide evidence that computing the maximum flow value between every pair
of nodes in a directed graph on $n$ nodes, $m$ edges,and capacities in the
range $[1..n]$, which we call the All-Pairs Max-Flow problem, cannot be solved
in time that is significantly faster (i.e., by a polynomial factor) than
$O(n^3)$ even for sparse graphs. Since a single maximum $st$-flow can be solved
in time $\tilde{O}(m\sqrt{n})$ [Lee and Sidford, FOCS 2014], we conclude that
the all-pairs version might require time equivalent to $\tilde\Omega(n^{3/2})$
computations of maximum $st$-flow,which strongly separates the directed case
from the undirected one. Moreover, if maximum $st$-flow can be solved in time
$\tilde{O}(m)$,then the runtime of $\tilde\Omega(n^2)$ computations is needed.
The latter settles a conjecture of Lacki, Nussbaum, Sankowski, and Wulf-Nilsen
[FOCS 2012] negatively.
  Specifically, we show that in sparse graphs $G=(V,E,w)$, if one can compute
the maximum $st$-flow from every $s$ in an input set of sources $S\subseteq V$
to every $t$ in an input set of sinks $T\subseteq V$ in time $O((|S| |T|
m)^{1-\epsilon})$,for some $|S|$, $|T|$, and a constant $\epsilon>0$,then
MAX-CNF-SAT with $n'$ variables and $m'$ clauses can be solved in time
${m'}^{O(1)}2^{(1-\delta)n'}$ for a constant $\delta(\epsilon)>0$,a problem for
which not even $2^{n'}/poly(n')$ algorithms are known. Such runtime for
MAX-CNF-SAT would in particular refute the Strong Exponential Time Hypothesis
(SETH). Hence, we improve the lower bound of Abboud, Vassilevska-Williams, and
Yu [STOC 2015], who showed that for every fixed $\epsilon>0$ and
$|S|=|T|=O(\sqrt{n})$, if the above problem can be solved in time
$O(n^{3/2-\epsilon})$, then some incomparable conjecture is false. Furthermore,
a larger lower bound than ours implies strictly super-linear time for maximum
$st$-flow problem, which would be an amazing breakthrough.
