Abstract
Our work concerns algorithms for a variant of Maximum Flow in unweighted graphs. In the AllPairs Connectivity (APC) problem, we are given a graph G on n vertices and m edges, and are tasked with computing the maximum number of edgedisjoint paths from s to t (equivalently, the size of a minimum (s,t)cut) in G, for all pairs of vertices (s,t). Over undirected graphs, it is known that APC can be solved in essentially optimal n^{2+o(1)} time. In contrast, 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.
Following [Abboud et al., ICALP 2019], we study a bounded version of APC called the kBounded All Pairs Connectivity (kAPC) problem. In this variant of APC, 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 mincut 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 Õ((kn)^ω) time algorithm solving kAPC in directed graphs. This is the first algorithm which solves kAPC faster than simply solving the more general APC problem exactly, for all k ≥ 3. This runtime is Õ(n^ω) for all k ≤ poly(log n), which essentially matches the optimal runtime for the k = 1 case of kAPC, under popular conjectures from finegrained complexity. Previously, this runtime was only achieved for general directed graphs when k ≤ 2 [Georgiadis et al., ICALP 2017]. Our result employs the same algebraic framework used in previous work, introduced by [Cheung, Lau, and Leung, 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 kAPC, it suffices to invert a lowrank random matrix instead of a generic random matrix.
We also obtain a new algorithm for a variant of kAPC, the kBounded AllPairs Vertex Connectivity (kAPVC) problem, where for every pair of vertices (s,t), we are now tasked with reporting the maximum number of internally vertexdisjoint (rather than edgedisjoint) paths from s to t if this number is less than k, and otherwise reporting that this number is at least k.
Our second result is an Õ(k²n^ω) time algorithm solving kAPVC in directed graphs. Previous work showed how to solve an easier version of the kAPVC problem (where answers only need to be returned for pairs of vertices (s,t) which are not edges in the graph) in Õ((kn)^ω) time [Abboud et al, ICALP 2019]. In comparison, our algorithm solves the full kAPVC problem, and is faster if ω > 2.
BibTeX  Entry
@InProceedings{akmal_et_al:LIPIcs.ICALP.2023.11,
author = {Akmal, Shyan and Jin, Ce},
title = {{An Efficient Algorithm for AllPairs Bounded Edge Connectivity}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {11:111:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18063},
URN = {urn:nbn:de:0030drops180632},
doi = {10.4230/LIPIcs.ICALP.2023.11},
annote = {Keywords: maximum flow, allpairs, connectivity, matrix rank}
}
Keywords: 

maximum flow, allpairs, connectivity, matrix rank 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 