Planar diameter via metric compression

DOI10.1145/3313276.3316358MaRDI QIDQ5212756zbMATH OpenOpenAlexFDO

Authors Jason Li, M. Parter

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.11491

zbMATH Keywords

diameterdistributed computingmetric compressionplanar graphsshortest path

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: 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 $SimesT$ distances using $widetildeO(|S|cdotpoly(D)+|T|)$ bits for unweighted graphs with diameter $D$. This significantly improves the state of the art of $widetildeO(|S|cdot{2}^D+|T|cdotD)$ bits. We also consider an approximate version of the problem for emph{weighted} graphs, where the goal is to encode $(1+epsilon)$ approximation of the $SimesT$ 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(D^5)$-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p. - There is an $widetildeO(D^3)+poly(logn/epsilon)cdot{D}^2$-round randomized distributed algorithm for computing an $(1+epsilon)$ 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 emph{exact} SSSP tree computation within $widetildeO(D^2)$ rounds.

Recommendations

• Near-optimal compression for the planar graph metric
• Faster approximate diameter and distance oracles in planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximating the diameter of planar graphs in near linear time

Cited in

(17)

• Packing and covering balls in graphs excluding a minor
• Low-congestion shortcut and graph parameters
• Near-optimal compression for the planar graph metric
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Mathematical Foundations of Computer Science 2005
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs
• Distributed planar reachability in nearly optimal time
• Distributed distance approximation
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Shortest path separators in unit disk graphs
• Going beyond surfaces in diameter approximation
• Efficient distributed decomposition and routing algorithms in minor-free networks and their applications
• Faster diameter computation in graphs of bounded Euler genus

This page was built for publication: Planar diameter via metric compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212756)