Near-additive spanners in low polynomial deterministic CONGEST time

DOI10.1145/3293611.3331635zbMATH Open1506.68071arXiv1903.00872OpenAlexW2963232515MaRDI QIDQ5145266FDOQ5145266

Shaked Matar, Michael Elkin

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: Given parameters $$, a subgraph $G^{\prime }=(V,H)$ of an $n$-vertex unweighted undirected graph $G=(V,E)$ is called an $$-spanner if for every pair $u,vinV$ of vertices, $$. If $$ the spanner is called a multiplicative $alpha$-spanner, and if $alpha=1+epsilon$, for an arbitrarily small $epsilon>0$, the spanner is said to be a near-additive one. Graph spanners are a fundamental and extremely well-studied combinatorial construct, with a multitude of applications in distributed computing and in other areas. Near-additive spanners, introduced in [EP01], preserve large distances much more faithfully than multiplicative spanners. Also, recent lower bounds [AB15] ruled out the existence of arbitrarily sparse purely additive spanners (i.e., spanners with $alpha=1$), and therefore near-additive spanners provide the best approximation of distances that one can hope for. Numerous distributed algorithms for constructing sparse near-additive spanners exist. In particular, there are now known efficient randomized algorithms in the CONGEST model that construct such spanners [EN17], and also there are efficient deterministic algorithms in the LOCAL model [DGPV09]. The only known deterministic CONGEST-model algorithm for the problem [Elk01] requires superlinear time in $n$. We remedy the situation and devise an efficient deterministic CONGEST-model algorithm for constructing arbitrarily sparse near-additive spanners. The running time of our algorithm is low polynomial, i.e., roughly $$, where $ho>0$ is an arbitrarily small positive constant that affects the additive term $$. In general, the parameters of our algorithm and of the resulting spanner are at the same ballpark as the respective parameters of the state-of-the-art randomized algorithm for the problem due to [EN17].

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

Recommendations

• Local Computation of Nearly Additive Spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• On the locality of distributed sparse spanner construction
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Additive spanners in nearly quadratic time

zbMATH Keywords

deterministic timegraph spannersCongest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed algorithms (68W15)

Cited In (6)

• Graph spanners: a tutorial review
• Local Computation of Nearly Additive Spanners
• An FPT Algorithm for Minimum Additive Spanner Problem.
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Distributed constructions of dual-failure fault-tolerant distance preservers
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners

This page was built for publication: Near-additive spanners in low polynomial deterministic CONGEST time

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