Conditional Lower Bounds for All-Pairs Max-Flow

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(n3) even for sparse graphs. Since a single maximum st-flow can be solved in time tildeO(m√n) [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to tildeOmega(n3/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 tildeO(m),then the runtime of tildeOmega(n2) 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 Ssubseteq V to every t in an input set of sinks Tsubseteq V in time O((|S| |T| m)1-ε),for some |S|, |T|, and a constant ε>0,then MAX-CNF-SAT with n' variables and m' clauses can be solved in time m'O(1)2(1-δ)n' for a constant δ(ε)>0,a problem for which not even 2n'/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 ε>0 and |S|=|T|=O(√n), if the above problem can be solved in time O(n3/2-ε), 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.