Abstract
AllPairs 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 finegrained equivalent to computing a rectangular MinPlus 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, AllPairs Longest Paths in DAGs with small weights, cRedAPSP in undirected graphs with small weights, for any c ≥ 2 (computing allpairs 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 finegrained reductions from directed unweighted APSP to AllPairs 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 MinPlus 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 nearoptimal Õ(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 AllPairs Shortest Paths}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {47:147:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14116},
URN = {urn:nbn:de:0030drops141166},
doi = {10.4230/LIPIcs.ICALP.2021.47},
annote = {Keywords: AllPairs Shortest Paths, FineGrained Complexity, Graph Algorithm}
}
Keywords: 

AllPairs Shortest Paths, FineGrained Complexity, Graph Algorithm 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 