Ultra-Sparse Near-Additive Emulators
share
Near-additive (aka (1+ϵ,β)-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch β. Specifically, for any pair of parameters ϵ >0, κ=1,2,…, one can have a (1+ϵ,β)-emulator with O(n^1+1/κ) edges, with β = (logκ/ϵ)^logκ. At their sparsest, these emulators employ c· n edges, for some constant c≥ 2. We tighten this bound, and show that in fact precisely n^1+1/κ edges suffice. In particular, our emulators can be ultra-sparse, i.e., we can have an emulator with n+o(n) edges and β = (loglog n/ϵ)^loglog n(1+o(1)). We also devise a distributed deterministic algorithm in the CONGEST model that builds these emulators in low polynomial time (i.e., in O(n^ρ) time, for an arbitrarily small constant parameter ρ >0). Finally, we also improve the state-of-the-art distributed deterministic -model construction of (1+ϵ,β)-spanners devised in the PODC'19 paper [ElkinM19]. Specifically, the spanners of [ElkinM19] have O(β· n^1+1/κ) edges, i.e., at their sparsest they employ O(loglog n/ϵ)^loglog n· n edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with O(n^1+1/κ) edges for κ = O(log n/log ^(3)n). At their sparsest, these spanners employ only O(n·loglog n) edges.
READ FULL TEXT