betaFeedback

WorksComputer Science

Improved Bounds on Distance Preservers

Abstract

Given an undirected unweighted graph GG on nn vertices and a set PP of pp pairs of its vertices, a distance preserver is a sparse subgraph of GG that exactly preserves the shortest-path distances between all pairs in PP. In this paper, we prove a new upper bound of O(n8/9p4/9)O(n^{8/9} p^{4/9}) for distance preservers when p∈[n1/2,n]p\in [n^{1/2}, n]. Our result improves the previous bound of O(n2/3p2/3+np1/3)O\big(n^{2/3}p^{2/3}+np^{1/3}\big) by Bodwin and Vassilevska Williams and O(min⁡{n+n1/2p, np1/2})O(\min\{n+n^{1/2}p,\,np^{1/2}\}) by Coppersmith and Elkin, particularly in the regime p∈[n7/10,n]p\in [n^{7/10}, n], and narrows the gap toward the conjectured O(n2/3p2/3+n)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+2 spanners with O(n+n9/10p2/5)O(n+n^{9/10}p^{2/5}) edges, pairwise additive +4+4 spanners with O(n+n24/25p8/25)O(n+n^{24/25}p^{8/25}) edges, and new bounds for sourcewise spanners, improving upon previous results in certain parameter regimes.

Introduction

Let G=(V,E)G=(V,E) be an nn-node undirected unweighted graph and let P⊆V×VP\subseteq V\times V be a set of p=∣P∣p=|P| demand pairs. A subgraph H=(V,EH)H=(V,E_H), where EH⊆EE_H\subseteq E, is called a distance preserver for (G,P)(G,P) if

dist⁡H(s,t)=dist⁡G(s,t)for every (s,t)∈P.\operatorname{dist}_{H}(s,t)=\operatorname{dist}_{G}(s,t)\qquad\text{for every }(s,t)\in P.

The goal is to determine its worst-case existential bound as a function of nn and pp, namely the minimum worst-case number of edges that always suffices for a distance preserver.

As a central object in graph sparsification/compression introduced by Coppersmith and Elkin [16], distance preservers have been studied extensively. By definition, for a graph GG and a set PP of demand pairs, a distance preserver for (G,P)(G,P) is essentially the union of, for each pair in PP, a shortest path in GG connecting them. The focus is how to choose these shortest paths, which we call a tie-breaking scheme. Coppersmith and Elkin [16] showed that a basic property a tiebreaking scheme can have is consistency, meaning that the intersection of any two chosen shortest paths is either empty or a subpath of both. With this property, they derived the size bound O(min⁡{n+n1/2p,np1/2})O(\min\{n+n^{1/2}p,np^{1/2}\}). When p=O(n1/2)p=O(n^{1/2}), their bound is O(n)O(n) and is clearly optimal. The remaining interesting regime is when p∈[n1/2,n2]p\in[n^{1/2},n^2].

A major advance was obtained by Bodwin and Vassilevska Williams [15]. They showed that consistency alone is not sufficient to obtain the optimal bound: there are consistent tie-breaking schemes whose unions achieve the Coppersmith-Elkin bound, but a different choice of shortest paths can be polynomially better. With further investigation on how the chosen shortest paths may branch with each other, they improved the upper bound to O(n2/3p2/3+np1/3)O(n^{2/3}p^{2/3}+np^{1/3}), which remained the best upper bound to date. Furthermore, they conjectured that it could be O(n2/3p2/3+n)O(n^{2/3}p^{2/3}+n). In other words, in the regime p∈[n1/2,n]p\in[n^{1/2},n], the bound is conjectured to be O(n2/3p2/3)O(n^{2/3}p^{2/3}), instead of only O(np1/3)O(np^{1/3}).

In this work, we make progress towards proving their conjecture. Our result can be summarized as the following theorem.

Theorem 1. Let GG be any nn-node undirected unweighted graph and let PP be any set of pp demand pairs with n1/2≤p≤nn^{1/2}\leq p\leq n. Then (G,P)(G,P) admits a distance preserver of O(n8/9p4/9)O(n^{8/9}p^{4/9}) edges.

Compared with previous results in [16] and [15], our bound achieves an improvement in the regime p∈[n7/10,n]p\in[n^{7/10},n]. See Figure 1 for comparison.

Figure 1. Comparison between our results and previous work.

Applications to additive spanners. Our techniques also yield new bounds for pairwise and sourcewise additive spanners. A pairwise additive +β+\beta spanner for (G,P)(G,P) is a subgraph H⊆GH \subseteq G satisfying dist⁡H(x,y)≤dist⁡G(x,y)+β\operatorname{dist}_H(x,y) \le\operatorname{dist}_G(x,y) + \beta for every (x,y)∈P(x,y) \in P. For arbitrary demand pairs, we obtain a +2+2 spanner with O(n+n9/10p2/5)O(n+n^{9/10}p^{2/5}) edges for all pp, and a +4+4 spanner with O(n+n24/25p8/25)O(n+n^{24/25}p^{8/25}) edges when p≤n7/6p \le n^{7/6}. We further obtain bounds that exploit a restricted source set: when P⊆S×VP \subseteq S \times V and σ=∣S∣\sigma= |S|, a common sampling reduction from our exact-preserver bound gives +2+2, +4+4, and +6+6 spanners whose sizes depend jointly on nn, pp, and σ\sigma. When all reachable pairs in S×VS \times V are demanded, an additional clustering reduction gives stronger complete-sourcewise guarantees. Table 1 summarizes these bounds, together with a further sourcewise +6+6 consequence of the classical exact-preserver bound.

ErrorPrevious boundsOur boundRangeImprovement rangeResult
Pairwise: arbitrary P⊆V×VP \subseteq V \times V
+2+2\min\left{\begin{gathered}n^{1/2}p\ [16],\quad np^{1/3}\ [12],\ n^{3/2}\ [21]\end{gathered}\right.n9/10p2/5n^{9/10}p^{2/5}All ppn2/3<p<n3/2n^{2/3}<p<n^{3/2}Theorem 27
+4+4\min\left{\begin{gathered}n^{1/2}p\ [16],\quad np^{2/7}\ [12],\ n^{9/10}p^{2/5}\ [16],\ n^{7/5}\ [19]\end{gathered}\right.n24/25p8/25n^{24/25}p^{8/25}p≤n7/6p\le n^{7/6}n3/4<p<n7/6n^{3/4}<p<n^{7/6}Theorem 36
Partially specified sourcewise: P⊆S×VP\subseteq S\times V
+2+2\min\left{\begin{gathered}n^{1/2}p\ [16],\quad np^{1/3}\ [12],\ n\sigma\ \text{(BFS trees)},\ n^{5/6}(p\sigma)^{1/3}\ [16],\ n(p\sigma)^{1/5}\ [15]\end{gathered}\right.n16/17(pσ)4/17n^{16/17}(p\sigma)^{4/17}pσ≤n5/3p\sigma\le n^{5/3}1110<a+b<53\frac{11}{10}<a+b<\frac{5}{3}, 26a−8b>1526a-8b>15, 12b<3+5a12b<3+5a, 13b>4a−113b>4a-1Theorem 37
+4+4\min\left{\begin{gathered}n^{1/2}p\ [16],\quad np^{2/7}\ [12],\ n\sigma\ \text{(BFS trees)},\ n^{9/10}p^{2/5}\ [16],\ n^{9/10}(p\sigma^2)^{1/5}\ [16],\ n(p\sigma^2)^{1/7}\ [15],\ n^{7/6}\sigma^{1/3}\ [31],\ n\max{\sigma^{1/2},p^{1/4}}\ [12]\end{gathered}\right.n24/25(pσ2)4/25n^{24/25}(p\sigma^2)^{4/25}pσ2≤n7/3p\sigma^2\le n^{7/3}a+2b>32a+2b>\frac{3}{2}, 17b>4a−117b>4a-1, 32b<4+9a32b<4+9a, 24a−2b<3124a-2b<31Theorem 37
+6+6\min\left{\begin{gathered}n^{1/2}p\ [16],\quad np^{1/4}\ [12],\ n\sigma\ \text{(BFS trees)},\ n^{13/14}(p\sigma^3)^{1/7}\ [16],\ n(p\sigma^3)^{1/9}\ [15],\ n^{9/8}\sigma^{3/8}\ [31],\ n^{6/5}\sigma^{1/5}\ [26],\ n(\sigma p)^{1/6}\ [26]\end{gathered}\right.n32/33(pσ3)4/33n^{32/33}(p\sigma^3)^{4/33}pσ3≤n3p\sigma^3\le n^3a+3b>1910a+3b>\frac{19}{10}, 13b<2+3a13b<2+3a, 32a−3b<4132a-3b<41, 20a+27b<3820a+27b<38Theorem 37
Complete sourcewise: P=S×VP=S\times V
+4+4\min\left{\begin{gathered}n\sigma\ \text{(BFS trees)},\ n^{7/6}\sigma^{1/3}\ [31]\end{gathered}\right.n8/7σ8/21n^{8/7}\sigma^{8/21}σ≤n1/2\sigma\le n^{1/2}n3/13<σ<n1/2n^{3/13}<\sigma<n^{1/2}Theorem 40
+6+6\min\left{\begin{gathered}n\sigma\ \text{(BFS trees)},\ n^{4/3}\ [9],\ n^{15/14}\sigma^{4/7}\ [16],\ n^{9/8}\sigma^{3/8}\ [31],\ n^{6/5}\sigma^{1/5}\ [26]\end{gathered}\right.n13/12σ1/2n^{13/12}\sigma^{1/2}All σ\sigman1/6<σ<n1/3n^{1/6}<\sigma<n^{1/3}Corollary 41
+6+6\min\left{\begin{gathered}n\sigma\ \text{(BFS trees)},\ n^{15/14}\sigma^{4/7}\ [16],\ n^{9/8}\sigma^{3/8}\ [31],\ n^{6/5}\sigma^{1/5}\ [26]\end{gathered}\right.n32/29σ12/29n^{32/29}\sigma^{12/29}σ≤n5/9\sigma\le n^{5/9}n13/64<σ<n14/31n^{13/64}<\sigma<n^{14/31}Theorem 40

Table 1. Additive spanner bounds, where n=∣V∣n=|V|, p=∣P∣p=|P|, and σ=∣S∣\sigma=|S|. Each entry ff denotes O(n+f)O(n+f) edges, with polylogarithmic factors suppressed in the previous bounds. Previous bounds are simplified on the range in the same row. For partial demands, write p=nap=n^a and σ=nb\sigma=n^b, with 0≤b≤10\le b\le1 and b≤a≤1+bb\le a\le1+b; every inequality in a cell must hold. Improvement means strict polynomial improvement over the previous bounds for fixed exponents, and does not compare different new rows against one another.

Comparison with previous bounds. We compare with the exact-preserver bound of [16], Bodwin’s logarithm-free +2+2, +4+4, and +6+6 bounds [12], and classical all-pairs spanners [21, 19, 9]; the +4+4 all-pairs bound is O~(n7/5)\widetilde{O}(n^{7/5}) [19]. The sourcewise comparisons additionally use [29, 31, 26]. We include the consequences of applying the same sampling reductions to the classical exact-preserver bounds of [16, 15], as well as consequences of the subsetwise +2+2 and rectangular +4+4 bounds in [12, 26]. In particular, n9/10p2/5n^{9/10}p^{2/5} for pairwise +4+4 and n15/14σ4/7n^{15/14}\sigma^{4/7} for complete-sourcewise +6+6 are classical-input consequences, not bounds stated explicitly in [16]. All comparisons include an additive O(n)O(n) term and take the minimum of the applicable constructions.

Related Work. Distance preservers have also been studied in many related forms. Bollobas, Coppersmith, and Elkin studied sparse DD-preservers and their connection to additive spanners [6]. Bodwin studied the linear-size regime, directed and weighted variants, large-pp behavior, and lower bounds for subset preservers [11]; related shortest-path structure, including unique shortest-path systems, was further investigated in [10]. Pairwise spanners and approximate preservers, where one allows multiplicative or additive error on the pairs in PP, have been studied in [17, 29, 26, 1, 2, 3, 30]. Special graph families and graph-metric compression have motivated distance-preserving subgraphs and emulators for planar graphs, interval graphs, and terminal metrics [4, 18, 24, 20]. Fault-tolerant distance preservers, which must preserve distances after edge or vertex failures, have been developed in [35, 32, 8, 23, 7, 13, 33 PP25]. Distance preservers also appear in or near the toolkit of distance oracles, additive spanners, hopsets, shortcut sets, and metric compression [34, 14, 22, 27, 28, 25]. Finally, optimization and algorithmic versions of finding minimum-size or minimum-weight preservers have begun to receive attention [5 SSV26].

Organization. The remainder of the paper is organized as follows. In Section 2, we start by providing an overview of our techniques. In Section 3, we present some formal definitions and important tools from previous work. Then in Section 4, we focus on a special case where the paths chosen by the tie-breaking scheme are edge-disjoint and show an upper bound of O(n5/6p1/2)O(n^{5/6}p^{1/2}). In Section 5, we establish the technical lemmas needed to handle shared edges in the general case. In Section 6, we combine these lemmas with an iterative demand-removal procedure to prove our main distance-preserver theorem. In Section 7, we adapt our framework to obtain the pairwise additive +2+2 spanner bound. Finally, Section 8 presents further results on pairwise and sourcewise additive spanners.

Technical Overview

In this section, we provide a high-level overview of our techniques for proving Theorem 1.

The Bodwin-Williams framework

We start by reviewing the approach of proving the O(n2/3p2/3+np1/3)O(n^{2/3}p^{2/3}+np^{1/3}) bound in [15]. The central notion in their analysis is branching events. Given a tie-breaking scheme π\pi, a branching event occurs when two selected paths enter the same vertex through two different incoming edges. Coppersmith and Elkin [16] showed that if π\pi has bb branching events, then its distance preserver contains O(n+nb)O(n+\sqrt{nb}) edges. Therefore, the goal is to prove better bounds for bb.

Bodwin and Williams showed that beyond consistency, a basic property of tie-breaking schemes requiring that any pair of selected paths share a (possibly empty) common subpath, we can also utilize edge essentiality, where each edge is essential to some demand pair in the sense that its removal will strictly increase the distance between this pair (note that if an edge is not essential to any pair, we can remove such an edge, only decreasing the size of the preserver). We say that an edge supports a demand pair if it is essential to it. Bodwin and Williams showed that, if many (p~\tilde{p}) demand pairs are supported by a cluster of (σ~\tilde{\sigma}) vertices that are close (at distance at most Δ\Delta) to each other, then these demand pairs can be handled together economically, using O(n+np~σ~Δ)O(n+\sqrt{n\tilde{p}\tilde{\sigma}\Delta}) edges.

This bound is then used iteratively. If the current preserver has average degree at least dd, then one can find a vertex of Ω(d)\Omega(d) degree-Ω(d)\Omega(d) neighbors, namely a constant-diameter cluster of Θ(d)\Theta(d) vertices that supports Ω(d2)\Omega(d^2) demand pairs. Handling these pairs requires O(n+nd3)O(n+\sqrt{nd^3}) edges. Remove those demands and repeat the process until the remaining graph has average degree at most dd.

In the range p≤np\le n, the main bottleneck is the O(n)O(n) term. As each round handles roughly d2d^2 demands, this accumulates to pd2⋅n\frac{p}{d^2}\cdot n. Balancing this with the O(nd)O(nd) leftover edges in an average-degree-dd graph gives d≈p1/3d\approx p^{1/3} and hence the O(np1/3)O(np^{1/3}) term in their bound.

Their framework is nice and clean, but also leaves some room for improvement: if we can manage to handle more than d2d^2 demands in one neighborhood, we will be able to improve the O(np1/3)O(np^{1/3}) bound.

Warm-up: the edge-disjoint case

We now describe our approach in a special case with the following simplifying assumptions.

  • there is a unique shortest path for each demand pair, and these paths are edge-disjoint; and

  • the degrees of all vertices are roughly the same, around dd, the average degree.

Clearly, in this case each edge ee is essential to the only demand pair whose shortest path contains ee.

We follow the same framework of Bodwin-Williams: find many demand pairs supported by a group of close vertices and handle them together. The main difference is: instead of only looking at constant-diameter neighborhoods of vertices, we explore neighborhoods with larger diameter, and the goal is to handle more than d2d^2 demand pairs in a single round.

On the surface, it is unclear that increasing the diameter will help at all. Consider the BFS tree from any vertex: it seems possible that each level contains dd vertices (so the growth is linear) and between consecutive levels there is a bi-clique between them, and all these edges come from the shortest paths of merely d2d^2 demand pairs.

References

  1. [1]Amir Abboud and Greg Bodwin. Error amplification for pairwise spanner lower bounds. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841–854, 2016.
  2. [2]Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. Journal of the ACM, 64(4):28:1–28:14, 2017.
  3. [3]Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568–576, 2017.
  4. [4]Amir Abboud, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal compression for the planar graph metric. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 530–549, 2018.arxiv.org/abs/1703.04814
  5. [5]Mojtaba Abdolmaleki, Yafeng Yin, and Neda Masoud. Minimum weight pairwise distance preservers. arXiv:2007.07554, 2020.arxiv.org/abs/2007.07554
  6. [6]Bela Bollobas, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. SIAM Journal on Discrete Mathematics, 19(4):1029–1055, 2005.
  7. [7]Greg Bodwin, Keerti Choudhary, Merav Parter, and Noa Shahar. New fault tolerant subset preservers. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 15:1–15:19, 2020.DOI
  8. [8]Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 73:1–73:14, 2017.arxiv.org/abs/1703.10293
  9. [9]Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α, β)-spanners. ACM Transactions on Algorithms, 7(1):5:1–5:26, 2010.DOI
  10. [10]Greg Bodwin. On the structure of unique shortest paths in graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2071–2089, 2019.arxiv.org/abs/1804.09745
  11. [11]Greg Bodwin. New results on linear size distance preservers. SIAM Journal on Computing, 50(2):662–673, 2021.arxiv.org/abs/1605.01106
  12. [12]Greg Bodwin. A note on distance-preserving graph sparsification. Information Processing Letters, 174:106205, 2022.arxiv.org/abs/2001.07741
  13. [13]Greg Bodwin and Merav Parter. Restorable shortest path tiebreaking for edge-faulty graphs. Journal of the ACM, 70(5):28:1–28:43, 2023.
  14. [14]Greg Bodwin and Virginia Vassilevska Williams. Very sparse additive spanners and emulators. In Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS), pages 377–382, 2015.arxiv.org/abs/1505.05630
  15. [15]Greg Bodwin and Virginia Vassilevska Williams. Better distance preservers and additive spanners. ACM Transactions on Algorithms, 17(4):36:1–36:24, 2021.
  16. [16]Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.DOI
  17. [17]Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On pairwise spanners. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 209–220, 2013.
  18. [18]Hsien-Chih Chang, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal distance emulator for planar graphs. In 26th Annual European Symposium on Algorithms (ESA), pages 16:1–16:17, 2018.arxiv.org/abs/1807.01478
  19. [19]Shiri Chechik. New additive spanners. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498–512. SIAM, 2013.
  20. [20]Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 36:1–36:14, 2017.arxiv.org/abs/1603.02321
  21. [21]Michael Elkin and David Peleg. (1 + ε, β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608–631, 2004.
  22. [22]Michael Elkin and Seth Pettie. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. ACM Transactions on Algorithms, 12(4):50:1–50:31, 2016.
  23. [23]Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 127:1–127:15, 2017.arxiv.org/abs/1704.06907
  24. [24]Kshitij Gajjar and Jaikumar Radhakrishnan. Distance-preserving subgraphs of interval graphs. In 25th Annual European Symposium on Algorithms (ESA), pages 39:1–39:13, 2017.arxiv.org/abs/1708.03081
  25. [25]Gary Hoppenworth, Yin zhan Xu, and Zixuan Xu. New separations and reductions for directed preservers and hopsets. arXiv:2411.08151, 2025.arxiv.org/abs/2411.08151
  26. [26]Telikepalli Kavitha. New pairwise spanners. Theory of Computing Systems, 61(4):1011–1036, 2017.DOI
  27. [27]Shimon Kogan and Merav Parter. Having hope in hops: New spanners, preservers and lower bounds for hopsets. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 766–777, 2022.arxiv.org/abs/2211.06920
  28. [28]Shimon Kogan and Merav Parter. Having hope in missing spanners: New distance preservers and light hopsets. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4352–4374, 2025.
  29. [29]Telikepalli Kavitha and Nithin M. Varma. Small stretch pairwise spanners and approximate d-preservers. SIAM Journal on Discrete Mathematics, 29(4):2239–2254, 2015.DOI
  30. [30]Ofer Neiman. On the size overhead of pairwise spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS), pages 83:1–83:22, 2024.arxiv.org/abs/2311.13673
  31. [31]Merav Parter. Bypassing Erdős’ girth conjecture: Hybrid stretch and sourcewise spanners. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part II, volume 8573 of Lecture Notes in Computer Science, pages 608–619. Springer, 2014.DOI
  32. [32]Merav Parter. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 481–490, 2015.
  33. [33]Merav Parter. Distributed constructions of dual-failure fault-tolerant distance preservers. arXiv:2010.01503, 2020.arxiv.org/abs/2010.01503
  34. [34]Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1):7:1–7:22, 2009.
  35. [35]Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In 21st Annual European Symposium on Algorithms (ESA), pages 779–790, 2013.arxiv.org/abs/1302.5401

Paper details

vlnc:W_dn4pfcta
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT 6-Astra

View statement
Looking for related papers…
Contents