research-article

Open access

Planar diameter via metric compression

Authors:

Jason Li,

Merav ParterAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 152 - 163

https://doi.org/10.1145/3313276.3316358

Published: 23 June 2019 Publication History

PDF eReader

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]. In our variant of the Planar Graph Metric Compression Problem, one is given an n-vertex planar graph G=(V,E), a set of S ⊆ V source terminals lying on a single face, and a subset of target terminals T ⊆ V. The goal is to compactly encode the S× T distances.

One of our key technical contributions is in providing a compression scheme that encodes all S × T distances using O(|S|·(D)+|T|) bits, for unweighted graphs with diameter D. This significantly improves the state of the art of O(|S|· 2^D+|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, for a given input parameter є ∈ (0,1]. Here, our compression scheme uses O((|S|/є)+|T|) bits. In addition, we describe how these compression schemes can be computed in near-linear time. At the heart of this compact compression scheme lies a VC-dimension type argument on planar graphs, using the well-known Sauer’’s lemma.

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 O(D⁵)-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p.

There is an O(D³)+D²(logn/є)-round randomized distributed algorithm for computing a (1+є) approximation for the diameter in weighted planar graphs, with unweighted diameter D, 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 O(D²) rounds.

References

[1]

Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-linear lower bounds for distributed distance computations, even in sparse networks. In International Symposium on Distributed Computing. Springer, 29–42.

Abstract

References

Cited By

Index Terms

Recommendations

Total domination in planar graphs of diameter two

Domination in planar graphs with small diameter

On 4-γt -critical graphs of diameter two

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations