2020/09/30 by Michael Elkin, Michael, Elkin, Shaked Matar +1
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2009.14729
We study a (1+\ε)-approximate single-source shortest paths\n(henceforth, (1+\ε)-SSSP) in n-vertex undirected, weighted graphs in\nthe parallel (PRAM) model of computation. A randomized algorithm with\npolylogarithmic time and slightly super-linear work \O(|E|\⋅\nn^\ρ), for an arbitrarily small \ρ>0, was given by Cohen [Coh94] more\nthan 25 years ago.\n Exciting progress on this problem was achieved in recent years\n[ElkinN17,ElkinN19,Li19,AndoniSZ19], culminating in randomized polylogarithmic\ntime and \O(|E|) work. However, the question of whether there exists a\ndeterministic counterpart of Cohen's algorithm remained wide open.\n In the current paper we devise the first deterministic polylogarithmic-time\nalgorithm for this fundamental problem, with work \O(|E|\⋅ n^\ρ),\nfor an arbitrarily small \ρ>0. This result is based on the first efficient\ndeterministic parallel algorithm for building hopsets, which we devise in this\npaper.\n