2019/12/24 by Jason Li, Li, Jason, Merav Parter +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1912.11491
openalex publication_date 2019/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [SODA'18]. One of our key technical contributions is in providing a compression scheme that encodes all S × T distances using \widetildeO(|S|⋅ poly(D)+|T|) bits for unweighted graphs with diameter D. This significantly improves the state of the art of \widetildeO(|S|⋅ 2D+|T| ⋅ D) bits. We also consider an approximate version of the problem for weighted graphs, where the goal is to encode (1+ε) approximation of the S × T distances. At the heart of this compact compression scheme lies a VC-dimension type argument on planar graphs. This efficient compression scheme leads to several improvements and simplifications in the setting of diameter computation, most notably in the distributed setting: - There is an \widetildeO(D5)-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p. - There is an \widetildeO(D3)+ poly(log n/ε)⋅ D2-round randomized distributed algorithm for computing an (1+ε) approximation of the diameter in weighted graphs with polynomially bounded weights, w.h.p. No sublinear round algorithms were known for these problems before. These distributed constructions are based on a new recursive graph decomposition that preserves the (unweighted) diameter of each of the subgraphs up to a logarithmic term. Using this decomposition, we also get an exact SSSP tree computation within \widetildeO(D2) rounds.