Faster Algorithms for All-Pairs Bounded Min-Cuts

Abstract : The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum s-t 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 k-bounded case, where the algorithm has to find all pairs with min-cut 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 ω) where ω < 2.38 is the matrix-multiplication 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) ω). This is only a factor k ω 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 ω). 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(√ log n) and k = o(log log n). The first super-cubic lower bound of n ω−1−o(1) k 2 time under the 4-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting k = n. For combinatorial algorithms, our reduction implies an n 2−o(1) k 2 conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC.
Document type :
Conference papers
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download
Contributor : Marie-France Sagot <>
Submitted on : Monday, October 28, 2019 - 9:18:59 AM
Last modification on : Tuesday, October 29, 2019 - 1:35:53 AM


Publisher files allowed on an open archive




Amir Abboud, Loukas Georgiadis, Giuseppe Italiano, Robert Krauthgamer, Nikos Parotsidis, et al.. Faster Algorithms for All-Pairs Bounded Min-Cuts. International Colloquium on Automata, Languages and Programming (ICALP), 2019, Patras, Greece. ⟨10.4230/LIPIcs.ICALP.2019.7⟩. ⟨hal-02335025⟩



Record views


Files downloads