An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Shyan Akmal, Ce Jin · Algorithmica · 2024
Abstract Our work concerns algorithms for a variant of in unweighted graphs. In the problem, we are given a graph G on n vertices and m edges, and are tasked with computing the maximum number of edge-disjoint paths from s to t (equivalently, the size of a minimum (s, t)-cut) in G, for all pairs of vertices (s, t). Significant algorithmic breakthroughs have recently shown that over undirected graphs, can be solved in $$n^{2+o(1)}$$ n 2 + o ( 1 ) time, which is essentially optimal. In contrast, the true time complexity of over directed graphs remains open: this problem can be solved in $${\tilde{O}}(m^\omega )$$ O ~ ( m ω ) time, where $$\omega \in [2, 2.373)$$ ω ∈ [ 2 , 2.373 ) is the exponent of matrix multiplication, but no matching conditional lower bound is known. Following [Abboud et al. In: 46th International colloquium on automata, languages, and programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019], we study a bounded version of $${{\textsf {APC}}}$$ APC called the k- (k- problem. In this variant of , we are given an integer k in addition to the graph G, and are now tasked with reporting the size of a minimum (s, t)-cut only for pairs (s, t) of vertices with min-cut value less than k (if the minimum (s, t)-cut has size at least k, we can just report it is “large” instead of computing the exact value). Our main result is an $${\tilde{O}}((kn)^\omega )$$ O ~ ( ( k n ) ω ) time algorithm solving k- in directed graphs. This is the first algorithm which solves k- faster than simply solving the more general problem exactly, for all $$k\ge 3$$ k ≥ 3 . This runtime is $${{\tilde{O}}}(n^\omega )$$ O ~ ( n ω ) for all $$k\le {{\,\textrm{poly}\,}}(\log n)$$ k ≤ poly ( log n ) , which essentially matches the optimal runtime for the $$k=1$$ k = 1 case of k-, under popular conjectures from fine-grained complexity. Previously, this runtime was only achieved for $$k\le 2$$ k ≤ 2 in general directed graphs [Georgiadis et al. In: 44th international colloquium on automata, languages, and programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017], and for $$k\le o(\sqrt{\log n})$$ k ≤ o ( log n ) in the special case of directed acyclic graphs [Abboud et al. In: 46th international colloquium on automata, languages, and programming, ICALP 2019, July 9–12, 2019, Patras, Greece, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019]. Our result employs the same algebraic framework used in previous work, introduced by [Cheung et al. In: FOCS, 2011]. A direct implementation of this framework involves inverting a large random matrix. Our new algorithm is based off the insight that for solving k-, it suffices to invert a low-rank random matrix instead of a generic random matrix. We also obtain a new algorithm for a variant of k-, the k- (k-) problem, where we are now tasked with reporting, for every pair of vertices (s, t), the maximum number of internally vertex-disjoint (rather than edge-disjoint) paths from