Akav, Maor ;
Roditty, Liam
A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs
Abstract
Let G = (V,E) be a weighted undirected graph with n vertices and m edges, and let d_G(u,v) be the length of the shortest path between u and v in G. In this paper we present a unified approach for obtaining algorithms for all pairs approximate shortest paths in weighted undirected graphs. For every integer k ≥ 2 we show that there is an Õ(n²+kn^{23/k}m^{2/k}) expected running time algorithm that computes a matrix M such that for every u,v ∈ V:
d_G(u,v) ≤ M[u,v] ≤ (2+(k2)/k)d_G(u,v).
Previous algorithms obtained only specific approximation factors. Baswana and Kavitha [FOCS 2006, SICOMP 2010] presented a 2approximation algorithm with expected running time of Õ(n²+m√ n) and a 7/3approximation algorithm with expected running time of Õ(n²+m^{2/3}n). Their results improved upon the results of Cohen and Zwick [SODA 1997, JoA 2001] for graphs with m = o(n²). Kavitha [FSTTCS 2007, Algorithmica 2012] presented a 5/2approximation algorithm with expected running time of Õ(n^{9/4}).
For k = 2 and k = 3 our result gives the algorithms of Baswana and Kavitha. For k = 4, we get a 5/2approximation algorithm with Õ(n^{5/4}m^{1/2}) expected running time. This improves upon the running time of Õ(n^{9/4}) due to Kavitha, when m = o(n²).
Our unified approach reveals that all previous algorithms are a part of a family of algorithms that exhibit a smooth tradeoff between approximation of 2 and 3, and are not sporadic unrelated results. Moreover, our new algorithm uses, among other ideas, the celebrated approximate distance oracles of Thorup and Zwick [STOC 2001, JACM 2005] in a non standard way, which we believe is of independent interest, due to their extensive usage in a variety of applications.
BibTeX  Entry
@InProceedings{akav_et_al:LIPIcs.ESA.2021.4,
author = {Akav, Maor and Roditty, Liam},
title = {{A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {4:14:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14585},
URN = {urn:nbn:de:0030drops145858},
doi = {10.4230/LIPIcs.ESA.2021.4},
annote = {Keywords: Graph algorithms, Approximate All Pairs of Shortest Paths, Distance Oracles}
}
31.08.2021
Keywords: 

Graph algorithms, Approximate All Pairs of Shortest Paths, Distance Oracles 
Seminar: 

29th Annual European Symposium on Algorithms (ESA 2021)

Issue date: 

2021 
Date of publication: 

31.08.2021 