Abboud, Amir ;
Georgiadis, Loukas ;
Italiano, Giuseppe F. ;
Krauthgamer, Robert ;
Parotsidis, Nikos ;
Trabelsi, Ohad ;
Uznanski, Przemyslaw ;
WollebGraf, Daniel
Faster Algorithms for AllPairs Bounded MinCuts
Abstract
The AllPairs MinCut problem (aka AllPairs MaxFlow) asks to compute a minimum st cut (or just its value) for all pairs of vertices s,t. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the kbounded case, where the algorithm has to find all pairs with mincut value less than k, and report only those. The most basic case k=1 is the Transitive Closure (TC) problem, which can be solved in graphs with n vertices and m edges in time O(mn) combinatorially, and in time O(n^{omega}) where omega<2.38 is the matrixmultiplication exponent. These time bounds are conjectured to be optimal.
We present new algorithms and conditional lower bounds that advance the frontier for larger k, as follows:
 A randomized algorithm for vertex capacities that runs in time {O}((nk)^{omega}). This is only a factor k^omega away from the TC bound, and nearly matches it for all k=n^{o(1)}.
 Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time {O}(2^{{O}(k^2)}* mn). The second algorithm can be faster on dense DAGs and runs in time {O}((k log n)^{4^{k+o(k)}}* n^{omega}). Previously, Georgiadis et al. [ICALP 2017], could match the TC bound (up to n^{o(1)} factors) only when k=2, and now our two algorithms match it for all k=o(sqrt{log n}) and k=o(log log n).
 The first supercubic lower bound of n^{omega1o(1)} k^2 time under the 4Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETHbased) lower bounds even in the unbounded setting k=n. For combinatorial algorithms, our reduction implies an n^{2o(1)} k^2 conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC.
Our three sets of results are obtained via different techniques. The first one adapts the network coding method of Cheung, Lau, and Leung [SICOMP 2013] to vertexcapacitated digraphs. The second set exploits new insights on the structure of latest cuts together with suitable algebraic tools. The lower bounds arise from a novel reduction of a different structure than the SETHbased constructions.
BibTeX  Entry
@InProceedings{abboud_et_al:LIPIcs:2019:10583,
author = {Amir Abboud and Loukas Georgiadis and Giuseppe F. Italiano and Robert Krauthgamer and Nikos Parotsidis and Ohad Trabelsi and Przemyslaw Uznanski and Daniel WollebGraf},
title = {{Faster Algorithms for AllPairs Bounded MinCuts}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {7:17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10583},
URN = {urn:nbn:de:0030drops105833},
doi = {10.4230/LIPIcs.ICALP.2019.7},
annote = {Keywords: Allpairs mincut, kreachability, network coding, Directed graphs, finegrained complexity}
}
2019
Keywords: 

Allpairs mincut, kreachability, network coding, Directed graphs, finegrained complexity 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 