License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.20
URN: urn:nbn:de:0030-drops-74264
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7426/
Go to the corresponding LIPIcs Volume Portal


Krauthgamer, Robert ; Trabelsi, Ohad

Conditional Lower Bounds for All-Pairs Max-Flow

pdf-format:
LIPIcs-ICALP-2017-20.pdf (0.8 MB)


Abstract

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 faster significantly (i.e., by a polynomial factor) than O(n^2 m). Since a single maximum st-flow in such graphs 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. This is in contrast to a conjecture of Lacki, Nussbaum, Sankowski, and Wulf-Nilsen [FOCS 2012] that All-Pairs Max-Flow in general graphs can be solved faster than the time of O(n^2) computations of maximum st-flow. 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 (maximum satisfiability of conjunctive normal form formulas) 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 (and intuitively weaker) 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. In addition, we show that All-Pairs Max-Flow in uncapacitated networks with every edge-density m=m(n), cannot be computed in time significantly faster than O(mn), even for acyclic networks. The gap to the fastest known algorithm by Cheung, Lau, and Leung [FOCS 2011] is a factor of O(m^{omega-1}/n), and for acyclic networks it is O(n^{omega-1}), where omega is the matrix multiplication exponent.

BibTeX - Entry

@InProceedings{krauthgamer_et_al:LIPIcs:2017:7426,
  author =	{Robert Krauthgamer and Ohad Trabelsi},
  title =	{{Conditional Lower Bounds for All-Pairs Max-Flow}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7426},
  URN =		{urn:nbn:de:0030-drops-74264},
  doi =		{10.4230/LIPIcs.ICALP.2017.20},
  annote =	{Keywords: Conditional lower bounds, Hardness in P, All-Pairs Maximum Flow, Strong Exponential Time Hypothesis}
}

Keywords: Conditional lower bounds, Hardness in P, All-Pairs Maximum Flow, Strong Exponential Time Hypothesis
Seminar: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 06.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI