A Hierarchy of Lower Bounds for Sublinear Additive Spanners

DOI10.1137/1.9781611974782.36zbMATH Open1410.68265arXiv1607.07497OpenAlexW2951064515MaRDI QIDQ4575773FDOQ4575773

Authors: Amir Abboud, Greg Bodwin, Seth Pettie 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $ildeO(n^{1+delta})$ bits. There is an inherent tradeoff between the sparsity parameter $delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. In this paper we show that the recent additive spanner lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that fully characterize the asymptotic behavior of the optimal stretch function $f$ as a function of $deltain(0,1/3)$. Specifically, for any integer $kge2$, any compression scheme with size $O(n^{1+frac12^k-1-epsilon})$ has a sublinear additive stretch function $f$: ${\displaystyle }$f(d) = d + Omega(d^{1-frac{1}{k}}).${\displaystyle }$ This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $$-spanners have an essentially optimal tradeoff between $delta,epsilon,$ and $$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of $(1+epsilon,O(k/epsilon{)}^{k-1})$-spanners with size $O((k/epsilon{)}^{h_k}k{n}^{1+frac12^{k+1}-1})$, where $h_k<3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved.

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

Recommendations

• A hierarchy of lower bounds for sublinear additive spanners
• Near-additive spanners in low polynomial deterministic CONGEST time
• Additive spanners in nearly quadratic time
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners and distance oracles in quadratic time
• Structural Information and Communication Complexity
• Additive Sparsification of CSPs.
• On additive approximate submodularity
• Near-additive spanners and near-exact hopsets, a unified view
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (19)

• Hopsets with constant hopbound, and applications to approximate shortest paths
• Improved guarantees for vertex sparsification in planar graphs
• Thorup-Zwick emulators are universally optimal hopsets
• An FPT Algorithm for Minimum Additive Spanner Problem.
• A hierarchy of lower bounds for sublinear additive spanners
• Near-optimal distance emulator for planar graphs
• Error Amplification for Pairwise Spanner Lower Bounds
• Very sparse additive spanners and emulators
• New results on linear size distance preservers
• Title not available (Why is that?)
• The 4/3 additive spanner exponent is tight
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Sparse weight tolerant subgraph for single source shortest path
• Improved weighted additive spanners
• The 4/3 additive spanner exponent is tight
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Title not available (Why is that?)

This page was built for publication: A Hierarchy of Lower Bounds for Sublinear Additive Spanners

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