arXiv preprint ·
Improved Bounds on Distance Preservers
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given an undirected unweighted graph $G$ on $n$ vertices and a set $P$ of $p$ pairs of its vertices, a distance preserver is a sparse subgraph of $G$ that exactly preserves the shortest-path distances between all pairs in $P$. In this paper, we prove a new upper bound of $O(n^{8/9} p^{4/9})$ for distance preservers when $p\in [n^{1/2}, n]$. Our result improves the previous bound of $O\big(n^{2/3}p^{2/3}+np^{1/3}\big)$ by Bodwin and Vassilevska Williams and $O(\min\{n+n^{1/2}p,\,np^{1/2}\})$ by Coppersmith and Elkin, particularly in the regime $p\in [n^{7/10}, n]$, and narrows the gap toward the conjectured $O(n^{2/3}p^{2/3}+n)$ bound. Using the techniques developed for distance preservers, we are also able to obtain pairwise additive $+2$ spanners with $O(n+n^{9/10}p^{2/5})$ edges, pairwise additive $+4$ spanners with $O(n+n^{24/25}p^{8/25})$ edges, and new bounds for sourcewise spanners, improving upon previous results in certain parameter regimes.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Quadratic-Time Barriers from Self-Referential SAT
Sublinear Metric Distortion for Matching
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.