License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.11
URN: urn:nbn:de:0030-drops-180632
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18063/
Akmal, Shyan ;
Jin, Ce
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Abstract
Our work concerns algorithms for a variant of Maximum Flow in unweighted graphs. 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). 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 k-Bounded All Pairs Connectivity (k-APC) 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 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 Õ((kn)^ω) time algorithm solving k-APC in directed graphs. This is the first algorithm which solves k-APC 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 k-APC, under popular conjectures from fine-grained 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 k-APC, 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-APC, the k-Bounded All-Pairs Vertex Connectivity (k-APVC) problem, where for every pair of vertices (s,t), we are now tasked with reporting the maximum number of internally vertex-disjoint (rather than edge-disjoint) 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 k-APVC in directed graphs. Previous work showed how to solve an easier version of the k-APVC 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 k-APVC 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 All-Pairs Bounded Edge Connectivity}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {11:1--11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18063},
URN = {urn:nbn:de:0030-drops-180632},
doi = {10.4230/LIPIcs.ICALP.2023.11},
annote = {Keywords: maximum flow, all-pairs, connectivity, matrix rank}
}
|
Keywords: |
|
maximum flow, all-pairs, connectivity, matrix rank |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
