Low Sensitivity Hopsets

Given a weighted graph G = (V, E, w), a (β, ε)-hopset H is an edge set such that for any s, t ∈ V, where s can reach t in G, there is a path from s to t in G∪H which uses at most β hops whose length is in the range [distG(s, t), (1 + ε)distG(s, t)]. We break away from the traditional question that asks for a hopset H that achieves small |H| and small diameter β and instead study the sensitivity of H, a new quality measure. The sensitivity of a vertex (or edge) given a hopset H is, informally, the number of times a single hop in G ∪ H bypasses it; a bit more formally, assuming shortest paths in G are unique, it is the number of hopset edges (s, t) ∈ H such that the vertex (or edge) is contained in the unique st-path in G having length exactly distG(s, t). The sensitivity associated with H is then the maximum sensitivity over all vertices (or edges). The highlights of our results are: A construction for (O^e(√n), 0)-hopsets on undirected graphs with O(log n) sensitivity, complemented with a lower bound showing that O^e(√n) is tight up to polylogarithmic factors for any construction with polylogarithmic sensitivity. A construction for (n^o(1), ε)-hopsets on undirected graphs with n^o(1) sensitivity for any ε > 0 that is at least inverse polylogarithmic, complemented with a lower bound on the tradeoff between β, ε, and the sensitivity. We define a notion of sensitivity for β-shortcut sets (which are the reachability analogues of hopsets) and give a construction for O^e(√n)-shortcut sets on directed graphs with O(log n) sensitivity, complemented with a lower bound showing that β = Ω(^e n^1/3) for any construction with polylogarithmic sensitivity. We believe hopset sensitivity is a natural measure in and of itself, and could potentially find use in a diverse range of contexts. More concretely, the notion of hopset sensitivity is also directly motivated by the Differentially Private All Sets Range Queries problem [Deng et al. WADS 23]. Our result for O(log n) sensitivity (O^e(√n), 0)-hopsets on undirected graphs immediately improves the current best-known upper bound on utility from O^e(n^1/3) to O^e(n^1/4) in the pure-DP setting, which is tight up to polylogarithmic factors.