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

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)

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

(19)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• 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
• Error Amplification for Pairwise Spanner Lower Bounds
• Near-optimal distance emulator for planar graphs
• Very sparse additive spanners and emulators
• New results on linear size distance preservers
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• 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

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)