An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
share
Our work concerns algorithms for an unweighted variant of Maximum Flow. In the All-Pairs Connectivity (APC) 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). Although over undirected graphs APC can be solved in essentially optimal n^2+o(1) time, the true time complexity of APC over directed graphs remains open: this problem can be solved in Õ(m^ω) time, where ω∈ [2, 2.373) is the exponent of matrix multiplication, but no matching conditional lower bound is known. We study a variant of APC called the k-Bounded All Pairs Connectivity (k-APC) problem. In this problem, we are given an integer k and graph G, and are tasked with reporting the size of a minimum (s,t)-cut only for pairs (s,t) of vertices with a minimum cut size less than k (if the minimum (s,t)-cut has size at least k, we just report it is "large" instead of computing the exact value). We present an algorithm solving k-APC in directed graphs in Õ((kn)^ω) time. This runtime is Õ(n^ω) for all k polylogarithmic in n, which is essentially optimal under popular conjectures from fine-grained complexity. Previously, this runtime was only known for k≤ 2 [Georgiadis et al., ICALP 2017]. We also study a variant of k-APC, the k-Bounded All-Pairs Vertex Connectivity (k-APVC) problem, which considers internally vertex-disjoint paths instead of edge-disjoint paths. We present an algorithm solving k-APVC in directed graphs in Õ(k^2n^ω) time. Previous work solved an easier version of the k-APVC problem in Õ((kn)^ω) time [Abboud et al, ICALP 2019].
READ FULL TEXT