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.2021.47
URN: urn:nbn:de:0030-drops-141166
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14116/
Chan, Timothy M. ;
Vassilevska Williams, Virginia ;
Xu, Yinzhan
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
Abstract
All-Pairs Shortest Paths (APSP) is one of the most well studied problems in graph algorithms. This paper studies several variants of APSP in unweighted graphs or graphs with small integer weights.
APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an Õ(n^ω) time algorithm, where ω < 2.373 is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be Ω(n^{2.5}) even if ω = 2 [Zwick'02]. To understand this n^{2.5} bottleneck, we build a web of reductions around directed unweighted APSP . We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of ω. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small (Õ(1)) integer weights, All-Pairs Longest Paths in DAGs with small weights, cRed-APSP in undirected graphs with small weights, for any c ≥ 2 (computing all-pairs shortest path distances among paths that use at most c red edges), #_{≤ c}APSP in directed graphs with small weights (counting the number of shortest paths for each vertex pair, up to c), and approximate APSP with additive error c in directed graphs with small weights, for c ≤ Õ(1).
We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with {0,1} weights and #_{mod c}APSP in directed unweighted graphs (computing counts mod c), thus showing that unless the current algorithms for APSP in directed unweighted graphs can be improved substantially, these problems need at least Ω(n^{2.528}) time.
We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights (previously studied by Zwick [STOC'99]) and for approximate APSP with sublinear additive error in directed unweighted graphs (previously studied by Roditty and Shapira [ICALP'08]). Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP (such as #_{≤ U}APSP and #_{mod U}APSP for U ≤ n^{Õ(1)}) in unweighted graphs, as well as a near-optimal Õ(n³)-time algorithm for the original #APSP problem in unweighted graphs (when counts may be exponentially large). This also implies an Õ(n³)-time algorithm for Betweenness Centrality, improving on the previous Õ(n⁴) running time for the problem. Our techniques also lead to a simpler alternative to Shoshan and Zwick’s algorithm [FOCS'99] for the original APSP problem in undirected graphs with small integer weights.
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs.ICALP.2021.47,
author = {Chan, Timothy M. and Vassilevska Williams, Virginia and Xu, Yinzhan},
title = {{Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {47:1--47:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14116},
URN = {urn:nbn:de:0030-drops-141166},
doi = {10.4230/LIPIcs.ICALP.2021.47},
annote = {Keywords: All-Pairs Shortest Paths, Fine-Grained Complexity, Graph Algorithm}
}
|
Keywords: |
|
All-Pairs Shortest Paths, Fine-Grained Complexity, Graph Algorithm |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
