Krauthgamer, Robert ;
Trabelsi, Ohad
Conditional Lower Bounds for AllPairs MaxFlow
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 AllPairs MaxFlow 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 stflow in such graphs can be solved in time \tilde{O}(m\sqrt{n}) [Lee and Sidford, FOCS 2014], we conclude that the allpairs version might require time equivalent to \tilde\Omega(n^{3/2}) computations of maximum stflow, 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 WulfNilsen [FOCS 2012] that AllPairs MaxFlow in general graphs can be solved faster than the time of O(n^2) computations of maximum stflow.
Specifically, we show that in sparse graphs G=(V,E,w), if one can compute the maximum stflow 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((STm)^{1epsilon}), for some S, T, and a constant epsilon>0, then MAXCNFSAT (maximum satisfiability of conjunctive normal form formulas) with n' variables and m' clauses can be solved in time {m'}^{O(1)}2^{(1delta)n'} for a constant delta(epsilon)>0, a problem for which not even 2^{n'}/\poly(n') algorithms are known. Such runtime for MAXCNFSAT would in particular refute the Strong Exponential Time Hypothesis (SETH). Hence, we improve the lower bound of Abboud, VassilevskaWilliams, 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/2epsilon}), then some incomparable (and intuitively weaker) conjecture is false. Furthermore, a larger lower bound than ours implies strictly superlinear time for maximum stflow problem, which would be an amazing breakthrough.
In addition, we show that AllPairs MaxFlow in uncapacitated networks with every edgedensity 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^{omega1}/n), and for acyclic networks it is O(n^{omega1}), 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 AllPairs MaxFlow}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {20:120:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7426},
URN = {urn:nbn:de:0030drops74264},
doi = {10.4230/LIPIcs.ICALP.2017.20},
annote = {Keywords: Conditional lower bounds, Hardness in P, AllPairs Maximum Flow, Strong Exponential Time Hypothesis}
}
07.07.2017
Keywords: 

Conditional lower bounds, Hardness in P, AllPairs Maximum Flow, Strong Exponential Time Hypothesis 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 