{"id":"arxiv:1911.01956","kind":"preprint","title":"Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators","authors":["Alexandr Andoni","Clifford Stein","Peilin Zhong"],"author_count":3,"year":2019,"published":"2019-11-05","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1911.01956","nct_id":null,"source_url":"https://arxiv.org/abs/1911.01956","archive_url":"https://space-kitty.com/papers/arxiv:1911.01956","updated":"2019-11-05","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1911.01956","abstract":"We present a $(1+\\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving $\\mathrm{poly}(\\log n)$ depth and $m\\mathrm{poly}(\\log n)$ work for $n$-nodes $m$-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For $(1+\\varepsilon)$-approximation, all prior algorithms with $\\mathrm{poly}(\\log n)$ depth perform at least $Ω(mn^{c})$ work for some constant $c>0$. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for $25$ years. We develop several new tools of independent interest. One of them is a new notion beyond hopsets --- low hop emulator --- a $\\mathrm{poly}(\\log n)$-approximate emulator graph in which every shortest path has at most $O(\\log\\log n)$ hops (edges). Direct applications of the low hop emulators are parallel algorithms for $\\mathrm{poly}(\\log n)$-approximate single source shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low diameter decomposition, all with $\\mathrm{poly}(\\log n)$ depth and $m\\mathrm{poly}(\\log n)$ work. To boost the approximation ratio to $(1+\\varepsilon)$, we introduce compressible preconditioners and apply it inside Sherman's framework (SODA'17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a $(1+\\varepsilon)$-approximate uncapacitated minimum cost flow in $\\mathrm{poly}(\\log n)$ depth using $m\\mathrm{poly}(\\log n)$ work. As a consequence, it also improves the state-of-the-art sequential running time from $m\\cdot 2^{O(\\sqrt{\\log n})}$ to $m\\mathrm{poly}(\\log n)$.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","cs.DC"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}