Near Tight Shortest Paths in the Hybrid Model

Shortest paths problems are subject to extensive studies in classic distributed models such as the CONGEST or congested clique, which describe the way in which nodes may communicate in order to solve such a problem. %where nodes initially know only the distance to their neighbors in some graph and must compute distances to any other node with as few communication rounds as possible. This article focuses on hybrid networks, which give nodes access to multiple, different modes of communication, in particular the HYBRID model which combines unrestricted local communication along edges of the input graph alongside heavily restricted global communication between arbitrary pairs of nodes. Previous work [Augustine et al, SODA'20, Kuhn et al. PODC'20] showed that each node learning its distance to $k$ dedicated source nodes (aka the $k$-SSP problem) takes at least $\tilOm(\!\sqrt{k})$ rounds in the HYBRID model, even for polynomial approximations. This lower bound was matched with algorithmic solutions for $k \geq n^{2/3}$. However, as $k$ gets smaller, the gap between the known upper and lower bounds diverges and even becomes exponential for the single source shortest paths problem (SSSP). In this work we plug this gap for the whole range of $k$ (up to terms that are polylogarithmic in $n$), by giving algorithmic solutions for $k$-SSP in $\tilO\big(\!\sqrt k\big)$ rounds for any $k$.