A Hierarchy of Lower Bounds for Sublinear Additive Spanners

DOI10.1137/1.9781611974782.36MaRDI QIDQ4575773zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(22)

• Thorup-Zwick emulators are universally optimal hopsets
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Very sparse additive spanners and emulators
• A hierarchy of lower bounds for sublinear additive spanners
• Error Amplification for Pairwise Spanner Lower Bounds
• The 4/3 additive spanner exponent is tight
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Near-optimal distance emulator for planar graphs
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• Sparse weight tolerant subgraph for single source shortest path
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Improved guarantees for vertex sparsification in planar graphs
• Hopsets with constant hopbound, and applications to approximate shortest paths
• The 4/3 additive spanner exponent is tight
• New results on linear size distance preservers
• An FPT Algorithm for Minimum Additive Spanner Problem.
• Improved weighted additive spanners
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• New fault tolerant subset preservers
• A unified framework for hopsets
• Lightweight near-additive spanners

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)