Introduction
Let G = ( V , E ) G=(V,E) G = ( V , E ) be an n n n -node undirected unweighted graph and let P ⊆ V × V P\subseteq V\times V P ⊆ V × V be a set of p = ∣ P ∣ p=|P| p = ∣ P ∣ demand pairs . A subgraph H = ( V , E H ) H=(V,E_H) H = ( V , E H ) , where E H ⊆ E E_H\subseteq E E H ⊆ E , is called a distance preserver for ( G , P ) (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. dist H ( s , t ) = dist G ( s , t ) for every ( s , t ) ∈ P .
The goal is to determine its worst-case existential bound as a function of n n n and p p p , 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 G G G and a set P P P of demand pairs, a distance preserver for ( G , P ) (G,P) ( G , P ) is essentially the union of, for each pair in P P P , a shortest path in G G G 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 + n 1 / 2 p , n p 1 / 2 } ) O(\min\{n+n^{1/2}p,np^{1/2}\}) O ( min { n + n 1/2 p , n p 1/2 }) . When p = O ( n 1 / 2 ) p=O(n^{1/2}) p = O ( n 1/2 ) , their bound is O ( n ) O(n) O ( n ) and is clearly optimal. The remaining interesting regime is when p ∈ [ n 1 / 2 , n 2 ] p\in[n^{1/2},n^2] p ∈ [ 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 ( n 2 / 3 p 2 / 3 + n p 1 / 3 ) O(n^{2/3}p^{2/3}+np^{1/3}) O ( n 2/3 p 2/3 + n p 1/3 ) , which remained the best upper bound to date. Furthermore, they conjectured that it could be O ( n 2 / 3 p 2 / 3 + n ) O(n^{2/3}p^{2/3}+n) O ( n 2/3 p 2/3 + n ) . In other words, in the regime p ∈ [ n 1 / 2 , n ] p\in[n^{1/2},n] p ∈ [ n 1/2 , n ] , the bound is conjectured to be O ( n 2 / 3 p 2 / 3 ) O(n^{2/3}p^{2/3}) O ( n 2/3 p 2/3 ) , instead of only O ( n p 1 / 3 ) O(np^{1/3}) O ( n p 1/3 ) .
In this work, we make progress towards proving their conjecture. Our result can be summarized as the following theorem.
Theorem 1. Let G G G be any n n n -node undirected unweighted graph and let P P P be any set of p p p demand pairs with n 1 / 2 ≤ p ≤ n n^{1/2}\leq p\leq n n 1/2 ≤ p ≤ n . Then ( G , P ) (G,P) ( G , P ) admits a distance preserver of O ( n 8 / 9 p 4 / 9 ) O(n^{8/9}p^{4/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 ∈ [ n 7 / 10 , n ] p\in[n^{7/10},n] p ∈ [ 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) ( G , P ) is a subgraph H ⊆ G H \subseteq G H ⊆ G satisfying dist H ( x , y ) ≤ dist G ( x , y ) + β \operatorname{dist}_H(x,y) \le\operatorname{dist}_G(x,y) + \beta dist H ( x , y ) ≤ dist G ( x , y ) + β for every ( x , y ) ∈ P (x,y) \in P ( x , y ) ∈ P . For arbitrary demand pairs, we obtain a + 2 +2 + 2 spanner with O ( n + n 9 / 10 p 2 / 5 ) O(n+n^{9/10}p^{2/5}) O ( n + n 9/10 p 2/5 ) edges for all p p p , and a + 4 +4 + 4 spanner with O ( n + n 24 / 25 p 8 / 25 ) O(n+n^{24/25}p^{8/25}) O ( n + n 24/25 p 8/25 ) edges when p ≤ n 7 / 6 p \le n^{7/6} p ≤ n 7/6 . We further obtain bounds that exploit a restricted source set: when P ⊆ S × V P \subseteq S \times V P ⊆ S × V and σ = ∣ S ∣ \sigma= |S| σ = ∣ S ∣ , a common sampling reduction from our exact-preserver bound gives + 2 +2 + 2 , + 4 +4 + 4 , and + 6 +6 + 6 spanners whose sizes depend jointly on n n n , p p p , and σ \sigma σ . When all reachable pairs in S × V S \times V S × V are demanded, an additional clustering reduction gives stronger complete-sourcewise guarantees. Table 1 summarizes these bounds, together with a further sourcewise + 6 +6 + 6 consequence of the classical exact-preserver bound.
Table 1. Additive spanner bounds, where n = ∣ V ∣ n=|V| n = ∣ V ∣ , p = ∣ P ∣ p=|P| p = ∣ P ∣ , and σ = ∣ S ∣ \sigma=|S| σ = ∣ S ∣ . Each entry f f f denotes O ( n + f ) 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 = n a p=n^a p = n a and σ = n b \sigma=n^b σ = n b , with 0 ≤ b ≤ 1 0\le b\le1 0 ≤ b ≤ 1 and b ≤ a ≤ 1 + b b\le a\le1+b b ≤ a ≤ 1 + 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 + 2 , + 4 +4 + 4 , and + 6 +6 + 6 bounds [12 ] , and classical all-pairs spanners [21 , 19 , 9 ] ; the + 4 +4 + 4 all-pairs bound is O ~ ( n 7 / 5 ) \widetilde{O}(n^{7/5}) 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 + 2 and rectangular + 4 +4 + 4 bounds in [12 , 26 ] . In particular, n 9 / 10 p 2 / 5 n^{9/10}p^{2/5} n 9/10 p 2/5 for pairwise + 4 +4 + 4 and n 15 / 14 σ 4 / 7 n^{15/14}\sigma^{4/7} n 15/14 σ 4/7 for complete-sourcewise + 6 +6 + 6 are classical-input consequences, not bounds stated explicitly in [16 ] . All comparisons include an additive O ( n ) 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 D D D -preservers and their connection to additive spanners [6 ] . Bodwin studied the linear-size regime, directed and weighted variants, large-p p p 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 P P P , 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 ( n 5 / 6 p 1 / 2 ) O(n^{5/6}p^{1/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 + 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 ( n 2 / 3 p 2 / 3 + n p 1 / 3 ) O(n^{2/3}p^{2/3}+np^{1/3}) O ( n 2/3 p 2/3 + n p 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 b b b branching events, then its distance preserver contains O ( n + n b ) O(n+\sqrt{nb}) O ( n + nb ) edges. Therefore, the goal is to prove better bounds for b b b .
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} 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 + n p ~ σ ~ Δ ) O(n+\sqrt{n\tilde{p}\tilde{\sigma}\Delta}) O ( n + n p ~ σ ~ Δ ) edges.
This bound is then used iteratively. If the current preserver has average degree at least d d d , then one can find a vertex of Ω ( d ) \Omega(d) Ω ( d ) degree-Ω ( d ) \Omega(d) Ω ( d ) neighbors, namely a constant-diameter cluster of Θ ( d ) \Theta(d) Θ ( d ) vertices that supports Ω ( d 2 ) \Omega(d^2) Ω ( d 2 ) demand pairs. Handling these pairs requires O ( n + n d 3 ) O(n+\sqrt{nd^3}) O ( n + n d 3 ) edges. Remove those demands and repeat the process until the remaining graph has average degree at most d d d .
In the range p ≤ n p\le n p ≤ n , the main bottleneck is the O ( n ) O(n) O ( n ) term. As each round handles roughly d 2 d^2 d 2 demands, this accumulates to p d 2 ⋅ n \frac{p}{d^2}\cdot n d 2 p ⋅ n . Balancing this with the O ( n d ) O(nd) O ( n d ) leftover edges in an average-degree-d d d graph gives d ≈ p 1 / 3 d\approx p^{1/3} d ≈ p 1/3 and hence the O ( n p 1 / 3 ) O(np^{1/3}) O ( n p 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 d 2 d^2 d 2 demands in one neighborhood, we will be able to improve the O ( n p 1 / 3 ) O(np^{1/3}) O ( n p 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 d d d , the average degree.
Clearly, in this case each edge e e e is essential to the only demand pair whose shortest path contains e e e .
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 d 2 d^2 d 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 d d d 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 d 2 d^2 d 2 demand pairs.
However, we show that this cannot happen. Let r r r be a radius parameter. Consider any vertex u u u . Since (we have assumed that) it has degree d d d and all its neighbors have degree d d d , the set P ∗ P^* P ∗ of demand pairs supported by its neighbors has size at least ∣ P ∗ ∣ = Ω ( d 2 ) |P^*| = \Omega(d^2) ∣ P ∗ ∣ = Ω ( d 2 ) . Consider now the radius-r r r ball of u u u : the shortest path of each of these demand pairs contributes a length-Θ ( r ) \Theta(r) Θ ( r ) subpath inside the ball. Since the paths are edge-disjoint, this gives Ω ( d 2 r ) \Omega(d^2r) Ω ( d 2 r ) local edges in the ball. On the other hand, since these d 2 d^2 d 2 demands are supported by the d d d neighbors of u u u , applying the BW bound to this neighborhood, we get that the number of local edges is at most O ( ∣ B ( u , r ) ∣ + ∣ B ( u , r ) ∣ ⋅ d 3 ) O(|B(u,r)| + \sqrt{|B(u,r)|}\cdot d^3) O ( ∣ B ( u , r ) ∣ + ∣ B ( u , r ) ∣ ⋅ d 3 ) . Comparing with the lower bound Ω ( d 2 r ) \Omega(d^2r) Ω ( d 2 r ) (and assuming r ≤ d r \le d r ≤ d ), we get that
∣ B ( u , r ) ∣ = Ω ( d r 2 ) . |B(u,r)| = \Omega(dr^2). ∣ B ( u , r ) ∣ = Ω ( d r 2 ) .
Therefore, the neighborhood growth of any vertex cannot be linear, but at least quadratic.
As a consequence, the r r r -neighborhood contains Ω ( d r 2 ⋅ d ) \Omega(dr^2 \cdot d) Ω ( d r 2 ⋅ d ) edges. Since each demand pair contributes O ( r ) O(r) O ( r ) edges in this neighborhood (between the first and last time a shortest path touches the ball, the path segment has length at most O ( r ) O(r) O ( r ) ), the r r r -neighborhood supports at least Ω ( d r 2 ⋅ d / r ) = Ω ( d 2 r ) \Omega(dr^2 \cdot d/r) = \Omega(d^2r) Ω ( d r 2 ⋅ d / r ) = Ω ( d 2 r ) demands, which is more than d 2 d^2 d 2 !
Applying the BW bound to handle all these demand pairs while balancing the other terms gives an advantage over the n p 1 / 3 np^{1/3} n p 1/3 bound. Moreover, it seems that the larger r r r we take, the greater advantage we will gain. However, there is one place in the discussion above that is not sufficiently rigorous: the shortest paths for the demands in P ∗ P^* P ∗ may contribute fewer than Ω ( d 2 r ) \Omega(d^2r) Ω ( d 2 r ) edges, as some of them may be simply shorter than r r r themselves. Luckily, these “short demands” can be handled separately and cheaply, with at most r r r edges per demand. We will consequently incur an additional O ( p r ) O(pr) O ( p r ) term in the distance preserver size bound. Re-balancing all of them, we can prove a bound of O ( n 5 / 6 p 1 / 2 ) O(n^{5/6}p^{1/2}) O ( n 5/6 p 1/2 ) , “half-way” between the Bodwin-Williams O ( n p 1 / 3 ) O(np^{1/3}) O ( n p 1/3 ) bound and their conjectured O ( n 2 / 3 p 2 / 3 ) O(n^{2/3}p^{2/3}) O ( n 2/3 p 2/3 ) bound.
We present the details for this warm-up case in Section 4. Remark: the second simplifying assumption (all vertices have degree around d d d ) is only for the purpose of technical overview; in Section 4 we can get rid of this assumption with some standard techniques.
Handling edge sharing: the general case
The edge-disjoint assumption is quite powerful since it implies the quadratic growth of any neighborhood, which is also the first thing we lose when the assumption is removed: the set P ∗ P^* P ∗ of demand pairs may share edges in their shortest paths, and so the local r r r -neighborhood is no longer guaranteed to contain Ω ( d 2 r ) \Omega(d^2r) Ω ( d 2 r ) edges, and the remaining analysis falls apart with it.
Therefore, in order to revive the analysis in the edge-disjoint case, it is instructive to first segregate the “edge-disjoint portion” of the shortest paths. This brings us to the first central notion: loyal edges.
Step 1: Loyal edges, and the assumption that most edges are loyal
Recall that every edge is essential: removing the edge will strictly increase the distance between some demand pair. If an edge is essential to only one demand pair, then this edge is its “private property”, and therefore the “edge-disjoint portion”. In fact, we can be more aggressive here: we say that an edge ( u , v ) (u,v) ( u , v ) is loyal if it is private and both u u u and v v v are incident to at least Ω ( d ) \Omega(d) Ω ( d ) other private edges (in this case we say both u u u and v v v are rich), where d d d is the average degree of the graph.
Although we cannot assume that all edges are loyal, it turns out that we only need to consider the case where most edges are loyal. This is because, intuitively
if a demand pair possesses few private edges, then it can be ignored (after the other demands are handled, we can return to handle them cheaply by adding only their private edges); therefore we can assume that most demand pairs possess many private edges, and so most edges are private; and
we then perform the following pruning: start with the subgraph induced by private edges (such a graph has average degree d ˉ = Ω ( d ) \bar{d} = \Omega(d) d ˉ = Ω ( d ) ), and repeatedly remove vertices with degree ≤ d ˉ / 10 \le\bar{d}/10 ≤ d ˉ /10 . Eventually, the total number of removed edges is below n d ˉ / 10 n\bar{d}/10 n d ˉ /10 , a small fraction of the private edges, and so in the remaining graph, all vertices are rich and all edges are loyal.
For the purpose of technical overview, we will make yet another simplifying assumption: every vertex is incident to d d d loyal edges and is therefore rich . With this simplification, the remaining analysis will be centered around loyal edges. For a vertex u u u and a radius parameter r r r , we define D ( u , r ) D(u,r) D ( u , r ) as the set of all demand pairs that possess a loyal edge within the r r r -neighborhood of u u u . From now on, our goal is to show that there exists some vertex u u u with ∣ D ( u , r ) ∣ |D(u,r)| ∣ D ( u , r ) ∣ significantly greater than d 2 d^2 d 2 .
Let α \alpha α be a parameter to be determined later. The goal is to find a vertex u u u such that ∣ D ( u , r ) ∣ > α d 2 |D(u,r)| > \alpha d^2 ∣ D ( u , r ) ∣ > α d 2 . Assume towards contradiction that ∣ D ( u , r ) ∣ ≤ α d 2 |D(u,r)| \le\alpha d^2 ∣ D ( u , r ) ∣ ≤ α d 2 for every u u u . The remainder of the proof consists of two steps: show that there is a large set of loyal edges, with every pair of them belonging to the same demand pair staying far from each other; and then show that there exists some small neighborhood that captures many edges in this set and therefore touches many distinct demand pairs.
Finding a dispersed set of loyal edges
By similar arguments, we can first derive that every radius-r r r neighborhood contains O ( α d r ) O(\alpha d r) O ( α d r ) vertices. This is since (i) any demand contributes only O ( r ) O(r) O ( r ) loyal edges incident to a radius-r r r ball, and so the total number of loyal edges in such a ball is O ( α d 2 r ) O(\alpha d^2 r) O ( α d 2 r ) ; and (ii) each vertex is incident to d d d loyal edges.
This neighborhood size bound implies a bound on the number of local loyal edges. Consider a vertex u u u . Let N l o y ( u ) N_{\mathrm{loy}}(u) N loy ( u ) be the set of loyal neighbors of u u u , and let P ( u ) P(u) P ( u ) be the set of demands that own a loyal edge incident to a vertex in N l o y ( u ) N_{\mathrm{loy}}(u) N loy ( u ) . By the Bodwin-Williams bound, handling these demands costs
λ ( u , r ) ≤ O ( ∣ B ( u , r ) ∣ ⋅ ∣ P ( u ) ∣ ⋅ ∣ N l o y ( u ) ∣ ) \lambda(u,r) \le O\left(\sqrt{|B(u,r)|\cdot|P(u)|\cdot|N_{\mathrm{loy}}(u)|}\right) λ ( u , r ) ≤ O ( ∣ B ( u , r ) ∣ ⋅ ∣ P ( u ) ∣ ⋅ ∣ N loy ( u ) ∣ )
edges. Since ∣ B ( u , r ) ∣ ≤ O ( α d r ) |B(u,r)| \le O(\alpha d r) ∣ B ( u , r ) ∣ ≤ O ( α d r ) , ∣ P ( u ) ∣ ≤ ∣ D ( u , r ) ∣ ≤ α d 2 |P(u)| \le|D(u,r)| \le\alpha d^2 ∣ P ( u ) ∣ ≤ ∣ D ( u , r ) ∣ ≤ α d 2 , and ∑ u ∣ N l o y ( u ) ∣ = O ( n d ) \sum_u |N_{\mathrm{loy}}(u)| = O(nd) ∑ u ∣ N loy ( u ) ∣ = O ( n d ) , summing over all vertices with Cauchy-Schwarz inequality, we get that ∑ u λ ( u , r ) ≤ O ( α n d 2 r 1 / 2 ) \sum_u \lambda(u,r) \le O(\alpha n d^2 r^{1/2}) ∑ u λ ( u , r ) ≤ O ( α n d 2 r 1/2 ) .
Let E l o y E^{\mathrm{loy}} E loy be the set of all loyal edges. For a loyal edge e e e , define
γ ( e , r ) = ∣ { f ∈ E l o y : dist H ( e , f ) ≤ r and f , e belong to the same demand pair } ∣ . \gamma(e,r) = \left|\{f \in E^{\mathrm{loy}} : \operatorname{dist}_{H}(e,f) \le r \text{ and } f,e \text{ belong to the same demand pair}\}\right|. γ ( e , r ) = { f ∈ E loy : dist H ( e , f ) ≤ r and f , e belong to the same demand pair } .
Note that if loyal edges f , e f,e f , e of the same demand pair lie within distance r r r from each other, then e e e is forced to appear in the local preserver (that is, contributes 1 1 1 to all λ ( u , r ) \lambda(u,r) λ ( u , r ) ) for all vertices u u u adjacent to an endpoint of f f f . Since all vertices are rich, each such f f f supplies Ω ( d ) \Omega(d) Ω ( d ) such vertices, and so
∑ e ∈ E l o y γ ( e , r ) ≤ O ( α n d r 1 / 2 ) . \sum_{e \in E^{\mathrm{loy}}} \gamma(e,r) \le O(\alpha n d r^{1/2}). e ∈ E loy ∑ γ ( e , r ) ≤ O ( α n d r 1/2 ) .
We now find a dispersed family of loyal edges. For each demand p p p , form a conflict graph on the loyal edges owned by p p p , joining two such edges if their distance in H H H is at most r r r . An independent set1 in this graph is a set of loyal edges owned by p p p that are pairwise farther than r r r . Applying the Caro–Wei bound to each demand separately and then using Cauchy–Schwarz, we obtain a set I ( r ) ⊆ E l o y I(r) \subseteq E^{\mathrm{loy}} I ( r ) ⊆ E loy such that no two edges of I ( r ) I(r) I ( r ) with the same owner are within distance r r r , and
∣ I ( r ) ∣ ≥ ∣ E l o y ∣ 2 ∑ e ∈ E l o y γ ( e , r ) ≥ Ω ( n d α r 1 / 2 ) , |I(r)| \ge\frac{|E^{\mathrm{loy}}|^2}{\sum_{e \in E^{\mathrm{loy}}} \gamma(e,r)} \ge\Omega\left(\frac{nd}{\alpha r^{1/2}}\right), ∣ I ( r ) ∣ ≥ ∑ e ∈ E loy γ ( e , r ) ∣ E loy ∣ 2 ≥ Ω ( α r 1/2 n d ) ,
using ∣ E l o y ∣ = Ω ( n d ) |E^{\mathrm{loy}}| = \Omega(nd) ∣ E loy ∣ = Ω ( n d ) .
Step 3: Capturing many loyal edges in a neighborhood
In graph G G G , choose centers greedily so that distinct centers are at least 2 r 2r 2 r apart; assign all vertices in B ( c , r ) B(c,r) B ( c , r ) to c c c , and assign every remaining vertex to a center within distance 2 r 2r 2 r , so every center hosts a cluster with diameter O ( r ) O(r) O ( r ) . Since every vertex has loyal degree Ω ( d ) \Omega(d) Ω ( d ) , ∣ B ( c , r ) ∣ ≥ Ω ( d r ) |B(c,r)| \ge\Omega(dr) ∣ B ( c , r ) ∣ ≥ Ω ( d r ) . Since the radius-r r r balls of all centers are disjoint, the number of clusters is at most O ( n d r ) O\left(\frac{n}{dr}\right) O ( d r n ) .
Consider now the separated set of edges computed in Step 2. By the pigeonhole principle, there must be some cluster B ( c , r ) B(c,r) B ( c , r ) that contains many selected loyal edges
∣ I ( r ) ∩ B ( c , r ) ∣ ≥ Ω ( ∣ I ( r ) ∣ n / ( d r ) ) = Ω ( d 2 r 1 / 2 α ) . |I(r) \cap B(c,r)| \ge\Omega\left(\frac{|I(r)|}{n/(dr)}\right) = \Omega\left(\frac{d^2r^{1/2}}{\alpha}\right). ∣ I ( r ) ∩ B ( c , r ) ∣ ≥ Ω ( n / ( d r ) ∣ I ( r ) ∣ ) = Ω ( α d 2 r 1/2 ) .
Since the edges in I ( r ) ∩ B ( c , r ) I(r) \cap B(c,r) I ( r ) ∩ B ( c , r ) are within distance O ( r ) O(r) O ( r ) from each other, from the property of set I ( r ) I(r) I ( r ) , each edge belongs to a distinct demand pair. Therefore, the center c c c sees Ω ( d 2 r 1 / 2 α ) \Omega\left(\frac{d^2r^{1/2}}{\alpha}\right) Ω ( α d 2 r 1/2 ) distinct demand pairs in its r r r -neighborhood. Balancing this with the assumption that ∣ D ( u , r ) ∣ ≤ α d 2 |D(u,r)| \le\alpha d^2 ∣ D ( u , r ) ∣ ≤ α d 2 holds for all u u u by taking α = Θ ( r 1 / 4 ) \alpha= \Theta(r^{1/4}) α = Θ ( r 1/4 ) , we get that there exists a vertex u u u with
∣ D ( u , r ) ∣ ≥ Ω ( d 2 r 1 / 4 ) . |D(u,r)| \ge\Omega(d^2r^{1/4}). ∣ D ( u , r ) ∣ ≥ Ω ( d 2 r 1/4 ) .
Although this is worse than the Ω ( d 2 r ) \Omega(d^2r) Ω ( d 2 r ) bound in the edge-disjoint case, we still manage to achieve the goal of discovering ω ( d 2 ) \omega(d^2) ω ( d 2 ) demands in a small neighborhood, which is enough for an improvement over the Bodwin-Williams n p 1 / 3 np^{1/3} n p 1/3 bound.
Preliminaries
Let G = ( V , E ) G = (V,E) G = ( V , E ) be an undirected unweighted simple graph with n = ∣ V ∣ n = |V| n = ∣ V ∣ . For each node u ∈ V u \in V u ∈ V , let N G ( u ) N_G(u) N G ( u ) be its set of neighbors, and let dist G ( u , v ) \operatorname{dist}_G(u,v) dist G ( u , v ) denote the shortest-path distance between u u u and v v v . For U ⊆ V U \subseteq V U ⊆ V , we use diam G ( U ) \operatorname{diam}_G(U) diam G ( U ) to denote the diameter in G G G .
For r ≥ 0 r \ge0 r ≥ 0 , define the radius-r r r neighborhood B G ( u , r ) = { v ∈ V : dist G ( u , v ) ≤ r } B_G(u,r) = \{v \in V : \operatorname{dist}_G(u,v) \le r\} B G ( u , r ) = { v ∈ V : dist G ( u , v ) ≤ r } ; in particular, B G ( u , 1 ) = N G ( u ) ∪ { u } B_G(u,1) = N_G(u) \cup\{u\} B G ( u , 1 ) = N G ( u ) ∪ { u } . The radius-r r r edge neighborhood is E G ( u , r ) = { e ∈ E : e ∩ B G ( u , r ) ≠ ∅ } E_G(u,r) = \{e \in E : e \cap B_G(u,r) \ne\varnothing\} E G ( u , r ) = { e ∈ E : e ∩ B G ( u , r ) = ∅ } .
Let P P P be a set of unordered vertex pairs, called a demand set , and write p = ∣ P ∣ p = |P| p = ∣ P ∣ . We assume demands are reachable between two distinct vertices.
Minimal Distance Preservers. We say a distance preserver H = ( V H , E H ) H = (V_H,E_H) H = ( V H , E H ) of ( G , P ) (G,P) ( G , P ) is minimal if, for every e ∈ E H e \in E_H e ∈ E H , the subgraph H ′ = ( V H , E H ∖ { e } ) H' = (V_H,E_H \setminus\{e\}) H ′ = ( V H , E H ∖ { e }) by deleting e e e is not a distance preserver of ( G , P ) (G,P) ( G , P ) . The minimality satisfies the following properties.
Lemma 2 ([16 ] ). Given an n n n -vertex graph G G G and a set P P P of p p p demand pairs, every minimal distance preserver of ( G , P ) (G,P) ( G , P ) has O ( n + p n ) O(n + p\sqrt{n}) O ( n + p n ) edges.
Lemma 3 [15 ] . Let S ⊆ V S \subseteq V S ⊆ V be nonempty, with ∣ S ∣ = σ \lvert S\rvert= \sigma ∣ S ∣ = σ and diam G ( S ) ≤ d \operatorname{diam}_G(S) \le d diam G ( S ) ≤ d , and let P ⊆ S × V P \subseteq S \times V P ⊆ S × V be the demand set of size ∣ P ∣ = p \lvert P\rvert= p ∣ P ∣ = p . For every minimal distance preserver H H H of ( G , P ) (G,P) ( G , P ) ,
∣ E H ∣ = O ( n + n p σ d ) . \lvert E_H\rvert= O\left(n + \sqrt{np\sigma d}\right). ∣ E H ∣ = O ( n + n p σ d ) .
We can further generalize Lemma 3 by a slight modification of the proof in [15 ] . For completeness, we give the proof in Section A.
Lemma 4 (Adapted from [15 ] ). Let S ⊆ V S \subseteq V S ⊆ V be nonempty, with ∣ S ∣ = σ \lvert S\rvert= \sigma ∣ S ∣ = σ and bounded diam G ( S ) ≤ d \operatorname{diam}_G(S) \le d diam G ( S ) ≤ d , and let P ⊆ S × V P \subseteq S \times V P ⊆ S × V be the demand set of size ∣ P ∣ = p \lvert P\rvert= p ∣ P ∣ = p . For every minimal distance preserver H H H of ( G , P ) (G,P) ( G , P ) and every U ⊆ V H U \subseteq V_H U ⊆ V H of size k k k , the subgraph H [ U ] = ( U , E H U ) H[U] = (U,E_H^U) H [ U ] = ( U , E H U ) of H H H induced by U U U has edge size
∣ E H U ∣ = O ( k + k p σ d ) . \lvert E_H^U\rvert= O\left(k + \sqrt{kp\sigma d}\right). ∣ E H U ∣ = O ( k + k p σ d ) .
Essential Edges. An edge e ∈ E H e \in E_H e ∈ E H is essential to q = ( s , t ) ∈ P q = (s,t) \in P q = ( s , t ) ∈ P in H H H if every shortest s s s –t t t path in H H H contains e e e . Define
D H P ( e ) = { q ∈ P : e is essential to q in H } . D_H^P(e) = \{q \in P : e\text{ is essential to }q\text{ in }H\}. D H P ( e ) = { q ∈ P : e is essential to q in H } .
We say that each demand in D H P ( e ) D_H^P(e) D H P ( e ) requires e e e , and write D ( e ) D(e) D ( e ) when H , P H,P H , P are clear. Minimality implies that every edge e ∈ E H e \in E_H e ∈ E H has D H P ( e ) ≠ ∅ D_H^P(e) \ne\varnothing D H P ( e ) = ∅ . Otherwise, all demands would retain shortest paths after deleting that edge. A demand-label l ( e ) l(e) l ( e ) is any member of D H P ( e ) D_H^P(e) D H P ( e ) .
Node Cover of Demands. Let H H H be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) . A node u ∈ V H u \in V_H u ∈ V H covers a demand q ∈ R q \in R q ∈ R if it is incident to an edge e e e essential to q q q , that is, q ∈ D H R ( e ) q \in D_H^R(e) q ∈ D H R ( e ) . In particular, every shortest path for q q q in H H H contains u u u . A set S ⊆ V H S \subseteq V_H S ⊆ V H covers Q ⊆ R Q \subseteq R Q ⊆ R if, for every q ∈ Q q \in Q q ∈ Q , some vertex of S S S covers $q.
Warm-up: the Edge-Disjoint Case
In this section, we consider a minimal distance preserver in which the demands can be connected by edge-disjoint shortest paths. We follow the same approach as in the general case: find many demands covered by a small set of nearby vertices, bound the number of edges needed for these demands, and remove them. The edge-disjoint assumption makes both the local counting argument and the demand-removal procedure simpler.
Theorem 5. Let G G G be an n n n -vertex undirected unweighted graph and let P P P be a set of p p p demand pairs, where n 2 / 3 ≤ p ≤ n n^{2/3} \le p \le n n 2/3 ≤ p ≤ n . Let H ⊆ G H \subseteq G H ⊆ G be a minimal distance preserver of ( G , P ) (G,P) ( G , P ) . Suppose that H H H contains one shortest path for each demand in P P P , with these paths mutually edge-disjoint. Then
∣ E ( H ) ∣ = O ( n 5 / 6 p 1 / 2 ) . \lvert E(H)\rvert= O(n^{5/6}p^{1/2}). ∣ E ( H )∣ = O ( n 5/6 p 1/2 ) .
Fix such paths and denote the path for a demand q q q by π ( q ) \pi(q) π ( q ) . For Q ⊆ P Q \subseteq P Q ⊆ P , write π ( Q ) = ⋃ q ∈ Q π ( q ) \pi(Q) = \bigcup_{q\in Q}\pi(q) π ( Q ) = ⋃ q ∈ Q π ( q ) for their union. In particular, π ( P ) ⊆ H \pi(P) \subseteq H π ( P ) ⊆ H already preserves every demand in P P P , so minimality of H H H implies H = π ( P ) H = \pi(P) H = π ( P ) . Throughout this section, retain all n n n vertices, including isolated vertices. All distances and balls are measured in H H H , including when we select vertices from a subgraph of H H H .
Essential edges and demand deletion. Every edge of π ( q ) \pi(q) π ( q ) is essential to q q q in H H H . Indeed, minimality makes it essential to some demand, while every other demand has a chosen path avoiding that edge. Thus every shortest path for q q q in H H H must contain every edge of π ( q ) \pi(q) π ( q ) , so π ( q ) \pi(q) π ( q ) is unique. Its subpaths are also unique shortest paths: replacing one by a different shortest path would give a different shortest path for q q q . Consequently, deleting a subset of demand paths leaves the other paths intact and unique. Their union is still a minimal distance preserver for the remaining demands. This lets us apply the same arguments throughout the demand-removal procedure.
Preserving a covered set of demands. Recall that a vertex covers a demand if it is incident to an edge essential to that demand. In our setting, a vertex covers a nontrivial demand q q q exactly when it lies on π ( q ) \pi(q) π ( q ) . Thus S S S covers Q Q Q if every path π ( q ) \pi(q) π ( q ) , q ∈ Q q \in Q q ∈ Q , meets S S S . Trivial demands need no edges and can be omitted from any set we cover.
Suppose nonempty S S S covers nonempty Q Q Q . For each q = ( s , t ) ∈ Q q=(s,t)\in Q q = ( s , t ) ∈ Q , choose u q ∈ S ∩ π ( q ) u_q\in S\cap\pi(q) u q ∈ S ∩ π ( q ) and split q q q into ( u q , s ) (u_q,s) ( u q , s ) and ( u q , t ) (u_q,t) ( u q , t ) . Let Q ∗ ⊆ S × V H Q^* \subseteq S\times V_H Q ∗ ⊆ S × V H be the resulting demand set, omitting trivial and repeated pairs, so ∣ Q ∗ ∣ ≤ 2 ∣ Q ∣ |Q^*|\le2|Q| ∣ Q ∗ ∣ ≤ 2∣ Q ∣ . Since u q u_q u q lies on a shortest path for q q q ,
dist H ( s , u q ) + dist H ( u q , t ) = dist H ( s , t ) . \operatorname{dist}_H(s,u_q)+\operatorname{dist}_H(u_q,t)=\operatorname{dist}_H(s,t). dist H ( s , u q ) + dist H ( u q , t ) = dist H ( s , t ) .
Preserving the two split pairs therefore preserves q q q . Moreover, their shortest paths in H H H are unique subpaths of π ( q ) \pi(q) π ( q ) , so their union is exactly π ( Q ) \pi(Q) π ( Q ) . In particular, π ( Q ) \pi(Q) π ( Q ) is a minimal distance preserver of ( H , Q ∗ ) (H,Q^*) ( H , Q ∗ ) .
Applying Lemma 4 with source set S S S gives, for every U ⊆ V H U\subseteq V_H U ⊆ V H ,
∣ E ( π ( Q ) [ U ] ) ∣ = O ( ∣ U ∣ + ∣ U ∣ ∣ Q ∣ ∣ S ∣ diam H ( S ) ) . (1) |E(\pi(Q)[U])|=O\left(|U|+\sqrt{|U||Q||S|\operatorname{diam}_H(S)}\right). \tag*{(1)} ∣ E ( π ( Q ) [ U ]) ∣ = O ( ∣ U ∣ + ∣ U ∣∣ Q ∣∣ S ∣ diam H ( S ) ) . (1)
If S S S is a singleton, the unique paths from its vertex form a tree, whose induced subgraph on U U U has at most ∣ U ∣ |U| ∣ U ∣ edges; hence the same bound holds when diam H ( S ) = 0 \operatorname{diam}_H(S)=0 diam H ( S ) = 0 . Taking U = V H U=V_H U = V H bounds all the edges of π ( Q ) \pi(Q) π ( Q ) , while taking U U U to be a ball bounds its local edges.
We will find the covering set using the following lemma.
Lemma 6. Suppose H H H has average degree at least d d d , every path π ( q ) \pi(q) π ( q ) has length at least r r r , and 1 ≤ r ≤ d 1\le r\le d 1 ≤ r ≤ d . There are sets Q ⊆ P Q\subseteq P Q ⊆ P and S ⊆ V H S\subseteq V_H S ⊆ V H such that S S S covers Q Q Q and
∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣ / d ) , diam H ( S ) ≤ 4 r . |Q|=\Omega(d^2r),\qquad|S|=O(|Q|/d),\qquad\operatorname{diam}_H(S)\le4r. ∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣/ d ) , diam H ( S ) ≤ 4 r .
The first bound ensures that each iteration removes many demands. The other two bounds make (1) small: the number of covering vertices is at most O ( ∣ Q ∣ / d ) O(|Q|/d) O ( ∣ Q ∣/ d ) , and these vertices are within distance O ( r ) O(r) O ( r ) of one another. We first use the lemma to prove the theorem, and then prove it by finding a dense subgraph, growing neighborhoods, and selecting covering vertices greedily.
Completing the Proof
Proof of Theorem 5. Fix parameters 1 ≤ r ≤ d 1\le r\le d 1 ≤ r ≤ d , whose values will be chosen at the end. First remove all demand paths of length less than r r r . There are at most p p p such paths, so this removes at most p r pr p r edges. Let H ′ H' H ′ be the union of the remaining paths, retaining all n n n vertices.
While H ′ H' H ′ has more than n d / 2 nd/2 n d /2 edges, its average degree exceeds d d d , and every remaining path has length at least r r r . We may therefore apply Lemma 6 to H ′ H' H ′ . It gives a demand set Q Q Q covered by S S S with ∣ Q ∣ = Ω ( d 2 r ) |Q| = \Omega(d^{2}r) ∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣ / d ) |S| = O(|Q|/d) ∣ S ∣ = O ( ∣ Q ∣/ d ) , and diam H ′ ( S ) ≤ 4 r \operatorname{diam}_{H'}(S) \le4r diam H ′ ( S ) ≤ 4 r . Using Equation (1) in H ′ H' H ′ with U = V H U = V_H U = V H , we get
∣ E ( π ( Q ) ) ∣ = O ( n + n ∣ Q ∣ ∣ S ∣ diam H ′ ( S ) ) = O ( n + ∣ Q ∣ n r d ) . |E(\pi(Q))| = O\left(n + \sqrt{n|Q||S|\operatorname{diam}_{H'}(S)}\right) = O\left(n + |Q|\sqrt{\frac{nr}{d}}\right). ∣ E ( π ( Q )) ∣ = O ( n + n ∣ Q ∣∣ S ∣ diam H ′ ( S ) ) = O ( n + ∣ Q ∣ d n r ) .
Here the second bound follows by substituting ∣ S ∣ = O ( ∣ Q ∣ / d ) |S| = O(|Q|/d) ∣ S ∣ = O ( ∣ Q ∣/ d ) and diam H ′ ( S ) = O ( r ) \operatorname{diam}_{H'}(S) = O(r) diam H ′ ( S ) = O ( r ) . Remove Q Q Q and its paths from H ′ H' H ′ . The remaining paths are still edge-disjoint and unique, so their union is again a minimal preserver and the procedure can continue.
Each iteration removes Ω ( d 2 r ) \Omega(d^{2}r) Ω ( d 2 r ) demands, and no demand is removed twice. There are therefore O ( p / ( d 2 r ) ) O(p/(d^{2}r)) O ( p / ( d 2 r )) iterations, so the O ( n ) O(n) O ( n ) term above contributes O ( n p / ( d 2 r ) ) O(np/(d^{2}r)) O ( n p / ( d 2 r )) edges in total. The terms proportional to ∣ Q ∣ |Q| ∣ Q ∣ sum to at most O ( p n r / d ) O(p\sqrt{nr/d}) O ( p n r / d ) , because the removed demand sets are disjoint subsets of P P P . At termination, at most n d / 2 nd/2 n d /2 edges remain. Including the short paths removed initially, we have accounted for every edge of H H H :
∣ E ( H ) ∣ = O ( p r + n p d 2 r + p n r d + n d ) . (2) |E(H)| = O\left(pr + \frac{np}{d^{2}r} + p\sqrt{\frac{nr}{d}} + nd\right). \tag*{(2)} ∣ E ( H ) ∣ = O ( p r + d 2 r n p + p d n r + n d ) . (2)
To choose the parameters, first balance the two terms contributed by the iterations. The equality n p / ( d 2 r ) = p n r / d np/(d^{2}r) = p\sqrt{nr/d} n p / ( d 2 r ) = p n r / d gives d r = n 1 / 3 dr = n^{1/3} d r = n 1/3 ; substituting this relation makes each term equal to n 2 / 3 p / d n^{2/3}p/d n 2/3 p / d . Balancing this with the final n d nd n d edges gives
d = n − 1 / 6 p 1 / 2 , r = n 1 / 2 p − 1 / 2 . d = n^{-1/6}p^{1/2}, \qquad r = n^{1/2}p^{-1/2}. d = n − 1/6 p 1/2 , r = n 1/2 p − 1/2 .
These values satisfy r ≥ 1 r \ge1 r ≥ 1 because p ≤ n p \le n p ≤ n , and r ≤ d r \le d r ≤ d because p ≥ n 2 / 3 p \ge n^{2/3} p ≥ n 2/3 . Each of the last three terms in Equation (2) is now n 5 / 6 p 1 / 2 n^{5/6}p^{1/2} n 5/6 p 1/2 . The short-path term is p r = n 1 / 2 p 1 / 2 ≤ n 5 / 6 p 1 / 2 pr = n^{1/2}p^{1/2} \le n^{5/6}p^{1/2} p r = n 1/2 p 1/2 ≤ n 5/6 p 1/2 , proving the theorem.
Growth of Local Neighborhoods
The main use of edge-disjointness is the following growth bound. Many demands pass through the neighbors of a vertex in a dense subgraph. Each contributes a long subpath inside a larger ball, and edge-disjointness lets us add their lengths. Comparing this edge count with Equation (1) forces the ball to contain many vertices.
Lemma 7. Suppose every path π ( q ) \pi(q) π ( q ) has length at least r r r , where 1 ≤ r ≤ d 1 \le r \le d 1 ≤ r ≤ d . Let H C = ( V ∗ , E C ) ⊆ H H_C = (V^{*}, E_C) \subseteq H H C = ( V ∗ , E C ) ⊆ H be a subgraph of minimum degree at least d / 4 d/4 d /4 . Then every u ∈ V ∗ u \in V^{*} u ∈ V ∗ satisfies
∣ B H ( u , r ) ∣ = Ω ( d r 2 ) . |B_H(u,r)| = \Omega(dr^{2}). ∣ B H ( u , r ) ∣ = Ω ( d r 2 ) .
Proof. If r < 2 r < 2 r < 2 , the at least d / 4 d/4 d /4 neighbors of u u u in H C H_C H C already give ∣ B H ( u , r ) ∣ = Ω ( d ) = Ω ( d r 2 ) |B_H(u,r)| = \Omega(d) = \Omega(dr^{2}) ∣ B H ( u , r ) ∣ = Ω ( d ) = Ω ( d r 2 ) . Assume r ≥ 2 r \ge2 r ≥ 2 . Choose S ⊆ N H C ( u ) S \subseteq N_{H_C}(u) S ⊆ N H C ( u ) of size ⌈ d / 4 ⌉ = Θ ( d ) \lceil d/4 \rceil= \Theta(d) ⌈ d /4 ⌉ = Θ ( d ) , and let P ′ P' P ′ be the demands whose paths meet S S S .
We first count these demands. Every vertex of S S S has degree at least d / 4 d/4 d /4 in H C H_C H C . On the other hand, any shortest path visits at most three neighbors of u u u : the subpath between its first and last such vertices has length at most two, using the route through u u u . At each of these vertices, the path uses at most two incident edges. Thus a demand accounts for at most six of the incidences counted in ∑ v ∈ S deg H C ( v ) \sum_{v\in S}\deg_{H_C}(v) ∑ v ∈ S deg H C ( v ) . Every core edge belongs to exactly one chosen path, so
∣ P ′ ∣ ≥ 1 6 ∑ v ∈ S deg H C ( v ) = Ω ( d 2 ) . |P'| \ge\frac{1}{6}\sum_{v\in S}\deg_{H_C}(v) = \Omega(d^{2}). ∣ P ′ ∣ ≥ 6 1 v ∈ S ∑ deg H C ( v ) = Ω ( d 2 ) .
Next fix q ∈ P ′ q \in P' q ∈ P ′ and a vertex of S S S on π ( q ) \pi(q) π ( q ) . Since the whole path has length at least r r r , one of its two directions from this vertex has at least r / 2 r/2 r /2 edges. The first ⌊ r / 2 ⌋ \lfloor r/2 \rfloor ⌊ r /2 ⌋ edges in that direction lie in B H ( u , r ) B_H(u,r) B H ( u , r ) : every vertex on this subpath is at distance at most 1 + ⌊ r / 2 ⌋ ≤ r 1+\lfloor r/2 \rfloor\le r 1 + ⌊ r /2 ⌋ ≤ r from u u u . This gives Ω ( r ) \Omega(r) Ω ( r ) local edges for each demand in P ′ P' P ′ . The paths are edge-disjoint, so these contributions add up to Ω ( ∣ P ′ ∣ r ) \Omega(|P'|r) Ω ( ∣ P ′ ∣ r ) edges.
Write x = ∣ B H ( u , r ) ∣ x=|B_H(u,r)| x = ∣ B H ( u , r ) ∣ . Since S S S covers P ′ P' P ′ , ∣ S ∣ = Θ ( d ) |S|=\Theta(d) ∣ S ∣ = Θ ( d ) , and diam H ( S ) ≤ 2 \operatorname{diam}_H(S)\le2 diam H ( S ) ≤ 2 , (1) gives
Ω ( ∣ P ′ ∣ r ) ≤ ∣ E ( π ( P ′ ) [ B H ( u , r ) ] ) ∣ ≤ O ( x + x ∣ P ′ ∣ d ) . \Omega(|P'|r)\le|E(\pi(P')[B_H(u,r)])|\le O\left(x+\sqrt{x|P'|d}\right). Ω ( ∣ P ′ ∣ r ) ≤ ∣ E ( π ( P ′ ) [ B H ( u , r )]) ∣ ≤ O ( x + x ∣ P ′ ∣ d ) .
At least one of the two terms in the upper bound must be Ω ( ∣ P ′ ∣ r ) \Omega(|P'|r) Ω ( ∣ P ′ ∣ r ) . The first gives x = Ω ( ∣ P ′ ∣ r ) x=\Omega(|P'|r) x = Ω ( ∣ P ′ ∣ r ) ; squaring the inequality for the second gives x = Ω ( ∣ P ′ ∣ r 2 / d ) x=\Omega(|P'|r^2/d) x = Ω ( ∣ P ′ ∣ r 2 / d ) . Therefore
x = Ω ( min { ∣ P ′ ∣ r , ∣ P ′ ∣ r 2 d } ) = Ω ( d r 2 ) , x=\Omega\left(\min\left\{|P'|r,\frac{|P'|r^2}{d}\right\}\right)=\Omega(dr^2), x = Ω ( min { ∣ P ′ ∣ r , d ∣ P ′ ∣ r 2 } ) = Ω ( d r 2 ) ,
since ∣ P ′ ∣ = Ω ( d 2 ) |P'|=\Omega(d^2) ∣ P ′ ∣ = Ω ( d 2 ) and r ≤ d r\le d r ≤ d .
Proof of the Covering Lemma
Proof of Lemma 6. Find a dense subgraph. Starting from H H H , repeatedly delete a vertex of current degree less than d / 4 d/4 d /4 . Charge each deleted edge to the vertex whose deletion removes it. Each vertex is charged fewer than d / 4 d/4 d /4 edges, so fewer than n d / 4 nd/4 n d /4 edges are deleted in total. Since H H H initially has at least n d / 2 nd/2 n d /2 edges, the remaining subgraph H C = ( V ∗ , E C ) H_C=(V^*,E_C) H C = ( V ∗ , E C ) satisfies
∣ E C ∣ ≥ n d / 4 , deg H C ( v ) ≥ d / 4 ( v ∈ V ∗ ) . |E_C|\ge nd/4,\qquad\deg_{H_C}(v)\ge d/4\quad(v\in V^*). ∣ E C ∣ ≥ n d /4 , deg H C ( v ) ≥ d /4 ( v ∈ V ∗ ) .
We use H C H_C H C only to select vertices and edges. The demand paths and all distances continue to be measured in H H H .
Find a neighborhood containing many demands. Choose centers greedily from V ∗ V^* V ∗ , adding a new center whenever it is at distance greater than 2 r 2r 2 r from every center already chosen. By Lemma 7, the radius-r r r ball around each center contains Ω ( d r 2 ) \Omega(dr^2) Ω ( d r 2 ) vertices. These balls are disjoint: a vertex in two of them would give a path of length at most 2 r 2r 2 r between their centers. There are consequently at most O ( n / ( d r 2 ) ) O(n/(dr^2)) O ( n / ( d r 2 )) centers. When the selection ends, every vertex of V ∗ V^* V ∗ is within distance 2 r 2r 2 r of a center, since otherwise it could be added as another center. Thus the radius-2 r 2r 2 r balls cover V ∗ V^* V ∗ .
For v ∈ V ∗ v\in V^* v ∈ V ∗ , let L ( v ) = { q ∈ P : v ∈ π ( q ) } L(v)=\{q\in P:v\in\pi(q)\} L ( v ) = { q ∈ P : v ∈ π ( q )} be the demands covered by v v v . A path uses at most two edges incident to v v v , giving
∣ L ( v ) ∣ ≥ 1 2 deg H C ( v ) ≥ d / 8 , ∑ v ∈ V ∗ ∣ L ( v ) ∣ ≥ ∣ E C ∣ ≥ n d / 4. |L(v)|\ge\frac{1}{2}\deg_{H_C}(v)\ge d/8,\qquad\sum_{v\in V^*}|L(v)|\ge|E_C|\ge nd/4. ∣ L ( v ) ∣ ≥ 2 1 deg H C ( v ) ≥ d /8 , v ∈ V ∗ ∑ ∣ L ( v ) ∣ ≥ ∣ E C ∣ ≥ n d /4.
The second inequality follows by summing the first degree bound: each edge of H C H_C H C is counted at both endpoints. Summing ∣ L ( v ) ∣ |L(v)| ∣ L ( v ) ∣ over the radius-2 r 2r 2 r balls counts every vertex of V ∗ V^* V ∗ at least once. As there are O ( n / ( d r 2 ) ) O(n/(dr^2)) O ( n / ( d r 2 )) such balls, one of them accounts for an Ω ( d r 2 / n ) \Omega(dr^2/n) Ω ( d r 2 / n ) fraction of this total. Its sum is therefore at least Ω ( d r 2 / n ) ⋅ ( n d / 4 ) = Ω ( d 2 r 2 ) \Omega(dr^2/n)\cdot(nd/4)=\Omega(d^2r^2) Ω ( d r 2 / n ) ⋅ ( n d /4 ) = Ω ( d 2 r 2 ) . Choose its center u ∗ u^* u ∗ and put B + = V ∗ ∩ B H ( u ∗ , 2 r ) B^+=V^*\cap B_H(u^*,2r) B + = V ∗ ∩ B H ( u ∗ , 2 r ) and σ = ∣ B + ∣ \sigma=|B^+| σ = ∣ B + ∣ . Then
Δ : = ∑ v ∈ B + ∣ L ( v ) ∣ = Ω ( d 2 r 2 ) , Δ ≥ σ d / 8. (3) \Delta:=\sum_{v\in B^+}|L(v)|=\Omega(d^2r^2),\qquad\Delta\ge\sigma d/8. \tag*{(3)} Δ := v ∈ B + ∑ ∣ L ( v ) ∣ = Ω ( d 2 r 2 ) , Δ ≥ σ d /8. (3)
Here Δ \Delta Δ counts pairs ( v , q ) (v,q) ( v , q ) with v ∈ B + v\in B^+ v ∈ B + covering q q q . A demand is counted at most 4 r + 1 4r+1 4 r + 1 times: its first and last vertices in B + B^+ B + have distance at most 4 r 4r 4 r via u ∗ u^* u ∗ , so the shortest subpath between them has at most 4 r + 1 4r+1 4 r + 1 vertices. This bounds all its visits to B + B^+ B + , even if the path leaves the ball between visits. Choose a small covering set. The preceding count guarantees many distinct demands in the ball. We also need to cover many of them using few vertices. Start with S = Q = ∅ S = Q = \varnothing S = Q = ∅ . Whenever a vertex v ∈ B + v \in B^{+} v ∈ B + covers at least Δ / ( 2 σ ) \Delta/(2\sigma) Δ/ ( 2 σ ) demands outside Q Q Q , add v v v to S S S and add L ( v ) L(v) L ( v ) to Q Q Q . Stop when no such vertex remains.
Every selected vertex adds at least Δ / ( 2 σ ) \Delta/(2\sigma) Δ/ ( 2 σ ) new demands. Since these newly covered demands are counted only once,
∣ S ∣ ≤ 2 σ Δ ∣ Q ∣ ≤ 16 d ∣ Q ∣ , |S| \le\frac{2\sigma}{\Delta}|Q| \le\frac{16}{d}|Q|, ∣ S ∣ ≤ Δ 2 σ ∣ Q ∣ ≤ d 16 ∣ Q ∣ ,
using the second bound in Equation (3) . At termination, each of the σ \sigma σ vertices covers fewer than Δ / ( 2 σ ) \Delta/(2\sigma) Δ/ ( 2 σ ) demands outside Q Q Q . Thus fewer than Δ / 2 \Delta/2 Δ/2 of the original pairs ( v , q ) (v,q) ( v , q ) involve uncovered demands, and at least Δ / 2 \Delta/2 Δ/2 involve demands in Q Q Q . Each demand is counted at most 4 r + 1 4r+1 4 r + 1 times, so
Δ 2 ≤ ∑ v ∈ B + ∣ L ( v ) ∩ Q ∣ ≤ ( 4 r + 1 ) ∣ Q ∣ . \frac{\Delta}{2} \le\sum_{v\in B^{+}} |L(v) \cap Q| \le(4r+1)|Q|. 2 Δ ≤ v ∈ B + ∑ ∣ L ( v ) ∩ Q ∣ ≤ ( 4 r + 1 ) ∣ Q ∣.
The first bound in Equation (3) now gives ∣ Q ∣ = Ω ( d 2 r ) |Q| = \Omega(d^{2}r) ∣ Q ∣ = Ω ( d 2 r ) . By construction, S S S covers Q Q Q , and S ⊆ B H ( u ∗ , 2 r ) S \subseteq B_H(u^{*},2r) S ⊆ B H ( u ∗ , 2 r ) gives diam H ( S ) ≤ 4 r \operatorname{diam}_H(S) \le4r diam H ( S ) ≤ 4 r .
The selection of separated centers and the greedy covering step are also used in the general case; Lemmas 18 and 19 give these arguments in the forms needed there. The additional work comes from allowing paths to share edges. In the neighborhood-growth proof, we used edge-disjointness to turn ∣ P ′ ∣ |P'| ∣ P ′ ∣ long subpaths into Ω ( ∣ P ′ ∣ r ) \Omega(|P'|r) Ω ( ∣ P ′ ∣ r ) distinct edges. In the demand-removal procedure, we used it to delete a demand’s path without affecting the other paths. The later sections replace these two uses by counting suitable essential edges and bounding the edges lost when covered demands are removed. The goal remains the same: cover many demands with few nearby vertices and use the distance-preserver bound for the split demands.
Technical Lemmas
Let H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) , with ∣ V H ∣ ≤ n |V_H|\le n ∣ V H ∣ ≤ n and ∣ E H ∣ ≤ n d |E_H|\le nd ∣ E H ∣ ≤ n d . For an edge e ∈ E H e\in E_H e ∈ E H , define
D ( e ) = { q ∈ R : every shortest path for q in H contains e } . D(e)=\{q\in R:\text{ every shortest path for }q\text{ in }H\text{ contains }e\}. D ( e ) = { q ∈ R : every shortest path for q in H contains e } .
Minimality implies D ( e ) ≠ ∅ D(e)\ne\varnothing D ( e ) = ∅ . An edge is private if ∣ D ( e ) ∣ = 1 |D(e)|=1 ∣ D ( e ) ∣ = 1 . Write Λ H = { e ∈ E H : ∣ D ( e ) ∣ = 1 } \Lambda_H=\{e\in E_H:|D(e)|=1\} Λ H = { e ∈ E H : ∣ D ( e ) ∣ = 1 } and Λ H ( q ) = { e ∈ Λ H : D ( e ) = { q } } \Lambda_H(q)=\{e\in\Lambda_H:D(e)=\{q\}\} Λ H ( q ) = { e ∈ Λ H : D ( e ) = { q }} . The private length of q q q is λ H ( q ) = ∣ Λ H ( q ) ∣ \lambda_H(q)=|\Lambda_H(q)| λ H ( q ) = ∣ Λ H ( q ) ∣ . For a private edge, we write D ( e ) = q D(e)=q D ( e ) = q to indicate D ( e ) = { q } D(e)=\{q\} D ( e ) = { q } . Assume that
λ H ( q ) ≥ l ( q ∈ R ) . (4) \lambda_H(q)\ge l \qquad(q\in R). \tag*{(4)} λ H ( q ) ≥ l ( q ∈ R ) . (4)
Definition 8 (Demand Cover). Let H H H be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) . A vertex x x x covers a demand q ∈ R q\in R q ∈ R if it is incident to an edge essential to q q q in H H H . A set S ⊆ V H S\subseteq V_H S ⊆ V H covers Q ⊆ R Q\subseteq R Q ⊆ R if every demand in Q Q Q is covered by a vertex of S S S .
Definition 9 (Demand Hitting). Let H H H be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) . A vertex u u u hits a demand q ∈ R q\in R q ∈ R if there are an edge e e e essential to q q q in H H H and an endpoint x ∈ e x\in e x ∈ e such that u x ∈ E H ux\in E_H ux ∈ E H . We call ( u , x , e ) (u,x,e) ( u , x , e ) a hitting tuple for q q q . A set S ⊆ V H S\subseteq V_H S ⊆ V H hits Q ⊆ R Q\subseteq R Q ⊆ R , or is a hitting set for Q Q Q , if every demand in Q Q Q has a hitting tuple whose first vertex belongs to S S S .
The technical hitting lemma below constructs these witnesses using loyal edges. The definition also permits other essential edges, as needed in § 7 .
We introduce a parameter r r r such that
6 ≤ r ≤ min { d 2 , l } , (5) 6 \le r \le\min\{d^2,l\}, \tag*{(5)} 6 ≤ r ≤ min { d 2 , l } , (5)
and we prove the following lemmas.
Lemma 10. Let H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) with ∣ V H ∣ ≤ n |V_H|\le n ∣ V H ∣ ≤ n , ∣ E H ∣ ≤ n d |E_H|\le nd ∣ E H ∣ ≤ n d , and ∣ Λ H ∣ ≥ n d / 20 |\Lambda_H|\ge nd/20 ∣ Λ H ∣ ≥ n d /20 . Suppose λ H ( q ) ≥ l \lambda_H(q)\ge l λ H ( q ) ≥ l for every q ∈ R q\in R q ∈ R . For every real parameter 6 ≤ r ≤ min { d 2 , l } 6\le r\le\min\{d^2,l\} 6 ≤ r ≤ min { d 2 , l } , there are Q ⊆ R Q\subseteq R Q ⊆ R and S ⊆ V H S\subseteq V_H S ⊆ V H such that S S S covers Q Q Q and
∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣ / d ) , diam H ( S ) = O ( r ) . |Q|=\Omega(d^2\sqrt{r}),\qquad|S|=O(|Q|/d),\qquad\operatorname{diam}_H(S)=O(r). ∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣/ d ) , diam H ( S ) = O ( r ) .
Lemma 11. Let H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) with ∣ V H ∣ ≤ n |V_H|\le n ∣ V H ∣ ≤ n and ∣ E H ∣ ≤ n d |E_H|\le nd ∣ E H ∣ ≤ n d . Suppose it has a loyal core as defined in Lemma 13 below, satisfying Equation (6) , and λ H ( q ) ≥ l \lambda_H(q)\ge l λ H ( q ) ≥ l for every q ∈ R q\in R q ∈ R . For every real parameter 6 ≤ r ≤ min { d 2 , l } 6\le r\le\min\{d^2,l\} 6 ≤ r ≤ min { d 2 , l } , there are Q ⊆ R Q\subseteq R Q ⊆ R and S ⊆ V H S\subseteq V_H S ⊆ V H such that S S S hits Q Q Q and
∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣ / d 2 ) , diam H ( S ) = O ( r ) . |Q|=\Omega(d^2\sqrt{r}),\qquad|S|=O(|Q|/d^2),\qquad\operatorname{diam}_H(S)=O(r). ∣ Q ∣ = Ω ( d 2 r ) , ∣ S ∣ = O ( ∣ Q ∣/ d 2 ) , diam H ( S ) = O ( r ) .
Overview. Lemmas 10 and 11 find a large set of demands witnessed by a small set of nearby vertices. The covering conclusion uses vertices incident to essential edges, while the hitting conclusion permits one additional adjacency. We first obtain many loyal edges whose labels have bounded local multiplicity. We then cluster vertices in decreasing order of ball volume and use Lemma 19 to select an efficient partial cover. § 6 will establish the private-length and density hypotheses needed to apply Lemma 10 to a changing residual graph.
Basic Tools
Shortest Paths and Their Neighbors. Fix an arbitrary shortest path π ( q ) \pi(q) π ( q ) in H H H for each q ∈ R q\in R q ∈ R . Every edge with q ∈ D ( e ) q\in D(e) q ∈ D ( e ) lies on every such path. We start from the following results.
Lemma 12. For every demand q ∈ R q\in R q ∈ R :
A vertex is incident to at most two edges essential to q q q .
For every vertex u u u , at most three vertices of π ( q ) \pi(q) π ( q ) belong to N H ( u ) N_H(u) N H ( u ) . Therefore, there are at most six pairs ( x , e ) (x,e) ( x , e ) where the edge e ∈ E H e\in E_H e ∈ E H is essential to q q q and x ∈ N H ( u ) x\in N_H(u) x ∈ N H ( u ) is an endpoint of e e e .
If e e e is essential to q q q and a subpath P P P of π ( q ) \pi(q) π ( q ) contains e e e , then every shortest path between the endpoints of P P P contains e e e .
Proof. For the first statement, every edge essential to q q q lies on the fixed simple path π ( q ) \pi(q) π ( q ) , which has at most two incident edges at a vertex. For the second statement, the first and last neighbors of u u u on the shortest path π ( q ) \pi(q) π ( q ) have distance at most two. Thus, at most three vertices of π ( q ) \pi(q) π ( q ) belong to N H ( u ) N_H(u) N H ( u ) . By the first statement, each such vertex is incident to at most two edges essential to q q q , giving at most six pairs ( x , e ) (x,e) ( x , e ) . For the third statement, let a , b a,b a , b be the two endpoints of the path P P P . Suppose there exists a shortest path between a a a and b b b avoiding e e e . Then there exists a shortest path for q q q avoiding e e e . This leads to a contradiction that e e e is essential to q q q . □
Dense Loyal Core. Suppose that H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) satisfies ∣ Λ H ∣ ≥ n d / 20 |\Lambda_H|\ge nd/20 ∣ Λ H ∣ ≥ n d /20 . The following pruning procedure gives a dense loyal core.
Lemma 13 (Dense loyal core). If ∣ Λ H ∣ ≥ n d / 20 |\Lambda_H|\ge nd/20 ∣ Λ H ∣ ≥ n d /20 , there is a subgraph H L = ( V ∗ , Λ H ∗ ) H_L=(V^*,\Lambda_H^*) H L = ( V ∗ , Λ H ∗ ) of H H H with nonempty vertex set V ∗ ⊆ V H V^*\subseteq V_H V ∗ ⊆ V H and edge set Λ H ∗ = { { u , v } ∈ Λ H : u , v ∈ V ∗ } \Lambda_H^*=\{\{u,v\}\in\Lambda_H:u,v\in V^*\} Λ H ∗ = {{ u , v } ∈ Λ H : u , v ∈ V ∗ } such that
m : = ∣ Λ H ∗ ∣ ≥ n d 40 , deg H L ( x ) ≥ d 40 ( x ∈ V ∗ ) . (6) m:=|\Lambda_H^*|\ge\frac{nd}{40},\qquad\deg_{H_L}(x)\ge\frac{d}{40}\quad(x\in V^*). \tag*{(6)} m := ∣ Λ H ∗ ∣ ≥ 40 n d , deg H L ( x ) ≥ 40 d ( x ∈ V ∗ ) . (6)
Proof. Start with ( V H , Λ H ) (V_H,\Lambda_H) ( V H , Λ H ) and repeatedly delete a vertex of current degree less than d / 40 d/40 d /40 . Each edge is counted only when it is deleted, so fewer than n d / 40 nd/40 n d /40 edges are deleted in total. At least n d / 40 nd/40 n d /40 edges remain, and every remaining vertex has degree at least d / 40 d/40 d /40 .
We call H L = ( V ∗ , Λ H ∗ ) H_L=(V^*,\Lambda_H^*) H L = ( V ∗ , Λ H ∗ ) a dense loyal core of the graph H H H . Vertices in V ∗ V^* V ∗ are rich, and edges in Λ H ∗ \Lambda_H^* Λ H ∗ are loyal. In addition, given a ≥ 0 a\ge0 a ≥ 0 , a node x ∈ V H x\in V_H x ∈ V H and demand q ∈ R q\in R q ∈ R , we define
B H ( x , a ) = { v : dist H ( x , v ) ≤ a } , E H ( x , a ) = { e ∈ E H : e ∩ B H ( x , a ) ≠ ∅ } , B H ∗ ( x , a ) = B H ( x , a ) ∩ V ∗ , Λ H ∗ ( x , a ) = E H ( x , a ) ∩ Λ H ∗ , Λ H ∗ ( x , a , q ) = { e ∈ Λ H ∗ ( x , a ) : D ( e ) = q } , λ H ∗ ( x , a , q ) = ∣ Λ H ∗ ( x , a , q ) ∣ . \begin{aligned}
B_H(x,a)&=\{v:\operatorname{dist}_H(x,v)\le a\},&
E_H(x,a)&=\{e\in E_H:e\cap B_H(x,a)\ne\varnothing\},\\
B_H^*(x,a)&=B_H(x,a)\cap V^*,&
\Lambda_H^*(x,a)&=E_H(x,a)\cap\Lambda_H^*,\\
\Lambda_H^*(x,a,q)&=\{e\in\Lambda_H^*(x,a):D(e)=q\},&
\lambda_H^*(x,a,q)&=|\Lambda_H^*(x,a,q)|.
\end{aligned} B H ( x , a ) B H ∗ ( x , a ) Λ H ∗ ( x , a , q ) = { v : dist H ( x , v ) ≤ a } , = B H ( x , a ) ∩ V ∗ , = { e ∈ Λ H ∗ ( x , a ) : D ( e ) = q } , E H ( x , a ) Λ H ∗ ( x , a ) λ H ∗ ( x , a , q ) = { e ∈ E H : e ∩ B H ( x , a ) = ∅ } , = E H ( x , a ) ∩ Λ H ∗ , = ∣ Λ H ∗ ( x , a , q ) ∣.
Growth of Local Balls. We prove a lower bound on the size of B H ( x , a ) B_H(x,a) B H ( x , a ) for every rich vertex x ∈ V ∗ x\in V^* x ∈ V ∗ .
Lemma 14. Suppose l ≥ 1 l\ge1 l ≥ 1 and the loyal core has minimum degree at least δ > 0 \delta>0 δ > 0 . For every rich vertex u u u and every real a ≥ 1 a\ge1 a ≥ 1 ,
∣ B H ( u , a ) ∣ ≥ δ 6 min { a , l } . (7) |B_H(u,a)|\ge\frac{\delta}{6}\min\{a,l\}. \tag*{(7)} ∣ B H ( u , a ) ∣ ≥ 6 δ min { a , l } . (7)
In particular, under Equation (6) , this is Ω ( d min { a , l } ) \Omega(d\min\{a,l\}) Ω ( d min { a , l }) .
Proof. Fix a positive integer j j j satisfying 2 ( j − 1 ) < l 2(j-1)<l 2 ( j − 1 ) < l , and define
L j = { v ∈ V H : dist H ( u , v ) = j } , W j = V ∗ ∩ B H ( u , j − 1 ) , b j = ∣ L j ∣ . L_j=\{v\in V_H:\operatorname{dist}_H(u,v)=j\},\qquad W_j=V^*\cap B_H(u,j-1),\qquad b_j=|L_j|. L j = { v ∈ V H : dist H ( u , v ) = j } , W j = V ∗ ∩ B H ( u , j − 1 ) , b j = ∣ L j ∣.
The set W j W_j W j is nonempty since u ∈ W j u\in W_j u ∈ W j . For each w ∈ L j w\in L_j w ∈ L j , fix an arbitrary shortest-path tree T w T_w T w rooted at w w w in its component of H H H . We claim
E ( H L [ W j ] ) ⊆ ⋃ w ∈ L j E ( T w [ W j ] ) . (8) E(H_L[W_j])\subseteq\bigcup_{w\in L_j}E(T_w[W_j]). \tag*{(8)} E ( H L [ W j ]) ⊆ w ∈ L j ⋃ E ( T w [ W j ]) . (8)
Indeed, take e ∈ E ( H L [ W j ] ) e\in E(H_L[W_j]) e ∈ E ( H L [ W j ]) and let q = D ( e ) q=D(e) q = D ( e ) . The path π ( q ) \pi(q) π ( q ) has length at least l > 2 ( j − 1 ) l>2(j-1) l > 2 ( j − 1 ) . If both endpoints of q q q belonged to B H ( u , j − 1 ) B_H(u,j-1) B H ( u , j − 1 ) , their distance would be at most 2 ( j − 1 ) 2(j-1) 2 ( j − 1 ) via u u u . Hence at least one endpoint of q q q is outside this ball. Orient the traversal of e e e along π ( q ) \pi(q) π ( q ) toward such an endpoint, start at the opposite endpoint of e e e , and stop at the first vertex w w w of L j L_j L j . The resulting subpath contains e e e . By Lemma 12, the tree path to w w w also contains e e e . Thus e ∈ T w e\in T_w e ∈ T w , and both endpoints of e e e lie in W j W_j W j , proving Equation (8) .
Each T w [ W j ] T_w[W_j] T w [ W j ] is a forest. Therefore
∣ E ( H L [ W j ] ) ∣ ≤ b j ∣ W j ∣ . (9) |E(H_L[W_j])|\le b_j|W_j|. \tag*{(9)} ∣ E ( H L [ W j ]) ∣ ≤ b j ∣ W j ∣. (9)
Every loyal neighbor of a vertex of W j W_j W j that is not itself in W j W_j W j belongs to L j L_j L j . Simplicity of the graph and the minimum degree assumption give
2 ∣ E ( H L [ W j ] ) ∣ ≥ ( δ − b j ) ∣ W j ∣ . (10) 2|E(H_L[W_j])|\ge(\delta-b_j)|W_j|. \tag*{(10)} 2∣ E ( H L [ W j ]) ∣ ≥ ( δ − b j ) ∣ W j ∣. (10)
Combining the last two inequalities and dividing by ∣ W j ∣ > 0 |W_j|>0 ∣ W j ∣ > 0 gives b j ≥ δ / 3 b_j \ge\delta/3 b j ≥ δ /3 . Now put J = min { ⌊ a ⌋ , ⌈ l / 2 ⌉ } J=\min\{\lfloor a\rfloor,\lceil l/2\rceil\} J = min {⌊ a ⌋ , ⌈ l /2 ⌉} . For every 1 ≤ j ≤ J 1\le j\le J 1 ≤ j ≤ J , the inequality 2 ( j − 1 ) < l 2(j-1)<l 2 ( j − 1 ) < l holds. These J J J layers are disjoint and belong to B H ( u , a ) B_H(u,a) B H ( u , a ) . Since a , l ≥ 1 a,l\ge1 a , l ≥ 1 , J ≥ 1 2 min { a , l } J\ge\frac{1}{2}\min\{a,l\} J ≥ 2 1 min { a , l } . Summing their sizes proves (7) .
Loyal Edges with Bounded Conflict
In this subsection, fix a radius satisfying (5) , and put n x = ∣ B H ( x , r ) ∣ n_x=|B_H(x,r)| n x = ∣ B H ( x , r ) ∣ for every rich vertex x x x . We prove the following lemmas.
Lemma 15 (Good Loyal Edges). Under (5) and (6) , there is a set Λ H ′ ⊆ Λ H ∗ \Lambda'_H\subseteq\Lambda^*_H Λ H ′ ⊆ Λ H ∗ , with ∣ Λ H ′ ∣ ≥ m / 2 = Ω ( n d ) |\Lambda'_H|\ge m/2=\Omega(nd) ∣ Λ H ′ ∣ ≥ m /2 = Ω ( n d ) , such that for every e ∈ Λ H ′ e\in\Lambda'_H e ∈ Λ H ′ and every endpoint x ∈ e x\in e x ∈ e ,
λ H ∗ ( x , r / 2 , D ( e ) ) ≤ C n x d r , (11) \lambda^*_H(x,r/2,D(e))\le C\frac{n_x}{d\sqrt{r}}, \tag*{(11)} λ H ∗ ( x , r /2 , D ( e )) ≤ C d r n x , (11) where n x = ∣ B H ( x , r ) ∣ n_x=|B_H(x,r)| n x = ∣ B H ( x , r ) ∣ for every rich vertex x x x and C C C is an absolute constant.
Lemma 16 (Localizing one demand label). Let Λ H ′ \Lambda'_H Λ H ′ be the good loyal edges supplied by Lemma 15, and fix an absolute constant A ≥ 0 A\ge0 A ≥ 0 . For F ⊆ Λ H ′ F\subseteq\Lambda'_H F ⊆ Λ H ′ , choose an endpoint x e x_e x e of every e ∈ F e\in F e ∈ F . Suppose that
n x e ≤ N ( e ∈ F ) , diam H ( { x e : e ∈ F } ) ≤ A r . n_{x_e}\le N\quad(e\in F),\qquad\operatorname{diam}_H(\{x_e:e\in F\})\le Ar. n x e ≤ N ( e ∈ F ) , diam H ({ x e : e ∈ F }) ≤ A r . Then every demand q ∈ R q\in R q ∈ R satisfies
∣ { e ∈ F : D ( e ) = q } ∣ = O ( N d r ) . (12) |\{e\in F:D(e)=q\}|=O\left(\frac{N}{d\sqrt{r}}\right). \tag*{(12)} ∣ { e ∈ F : D ( e ) = q } ∣ = O ( d r N ) . (12) The implicit constant may depend on A A A .
To prove Lemmas 15 and 16, we prove the following result.
Lemma 17. Under (5) and (6) ,
Z : = ∑ x ∈ V ∗ ∑ e ∈ Λ H ∗ x ∈ e λ H ∗ ( x , r / 2 , D ( e ) ) n x = O ( m d r ) . (13) Z:=\sum_{x\in V^*}\sum_{\substack{e\in\Lambda^*_H\\x\in e}}\frac{\lambda^*_H(x,r/2,D(e))}{n_x}=O\left(\frac{m}{d\sqrt{r}}\right). \tag*{(13)} Z := x ∈ V ∗ ∑ e ∈ Λ H ∗ x ∈ e ∑ n x λ H ∗ ( x , r /2 , D ( e )) = O ( d r m ) . (13)
Proof. Let k = ⌈ d / 40 ⌉ k=\lceil d/40\rceil k = ⌈ d /40 ⌉ . Since (5) implies d ≥ 6 d\ge\sqrt{6} d ≥ 6 , we have k = Θ ( d ) k=\Theta(d) k = Θ ( d ) . Partition N H L ( x ) N_{H_L}(x) N H L ( x ) into bundles, each of size between k k k and 2 k − 1 2k-1 2 k − 1 . This is possible since deg H L ( x ) ≥ k \deg_{H_L}(x)\ge k deg H L ( x ) ≥ k : form bundles of size k k k and merge any nonempty final remainder into the preceding bundle. Let B x ( z ) B_x(z) B x ( z ) denote the bundle containing the neighbor z z z of x x x . Every bundle has size Θ ( d ) \Theta(d) Θ ( d ) .
For each incidence ( x , e ) (x,e) ( x , e ) with e = { x , z } ∈ Λ H ∗ e=\{x,z\}\in\Lambda^*_H e = { x , z } ∈ Λ H ∗ , charge 1 / n x 1/n_x 1/ n x to every pair ( y , f ) (y,f) ( y , f ) such that
y ∈ B x ( z ) , f ∈ Λ H ∗ ( x , r / 2 , D ( e ) ) . (14) y\in B_x(z),\qquad f\in\Lambda^*_H(x,r/2,D(e)). \tag*{(14)} y ∈ B x ( z ) , f ∈ Λ H ∗ ( x , r /2 , D ( e )) . (14)
The total charge is
T = ∑ x ∈ V ∗ ∑ e = { x , z } ∈ Λ H ∗ ∣ B x ( z ) ∣ λ H ∗ ( x , r / 2 , D ( e ) ) n x = Θ ( d Z ) . (15) T=\sum_{x\in V^*}\sum_{\substack{e=\{x,z\}\in\Lambda^*_H}}\frac{|B_x(z)|\lambda^*_H(x,r/2,D(e))}{n_x}=\Theta(dZ). \tag*{(15)} T = x ∈ V ∗ ∑ e = { x , z } ∈ Λ H ∗ ∑ n x ∣ B x ( z ) ∣ λ H ∗ ( x , r /2 , D ( e )) = Θ ( d Z ) . (15)
Fix a rich vertex y y y , and put
d y = deg H L ( y ) , U y = B H ( y , r / 2 + 2 ) , u y = ∣ U y ∣ . d_y=\deg_{H_L}(y),\qquad U_y=B_H(y,r/2+2),\qquad u_y=|U_y|. d y = deg H L ( y ) , U y = B H ( y , r /2 + 2 ) , u y = ∣ U y ∣.
For each x ∈ N H L ( y ) x \in N_{H_L}(y) x ∈ N H L ( y ) and each z z z in the bundle of x x x containing y y y , let q = D ( { x , z } ) = ( s , t ) q = D(\{x,z\}) = (s,t) q = D ({ x , z }) = ( s , t ) . Add ( x , s ) (x,s) ( x , s ) and ( x , t ) (x,t) ( x , t ) to a demand set Q y Q_y Q y ; trivial pairs may be omitted. Repetitions are removed. Then
Q y ⊆ N H L ( y ) × V H , ∣ Q y ∣ ≤ 4 k d y = O ( d d y ) . Q_y \subseteq N_{H_L}(y) \times V_H,\qquad|Q_y| \le4kd_y = O(dd_y). Q y ⊆ N H L ( y ) × V H , ∣ Q y ∣ ≤ 4 k d y = O ( d d y ) .
All vertices of N H L ( y ) N_{H_L}(y) N H L ( y ) are at distance at most two from one another in H H H . Choose a minimal distance preserver H y ⊆ H H_y \subseteq H H y ⊆ H for ( H , Q y ) (H,Q_y) ( H , Q y ) . Applying Lemma 4 with source set N H L ( y ) N_{H_L}(y) N H L ( y ) , ∣ Q y ∣ = O ( d d y ) |Q_y| = O(dd_y) ∣ Q y ∣ = O ( d d y ) , and vertex set U y U_y U y gives
∣ E ( H y [ U y ] ) ∣ = O ( u y + d y d u y ) . (16) |E(H_y[U_y])| = O(u_y + d_y\sqrt{du_y}). \tag*{(16)} ∣ E ( H y [ U y ]) ∣ = O ( u y + d y d u y ) . (16)
If an incidence ( x , e ) (x,e) ( x , e ) charges ( y , f ) (y,f) ( y , f ) , the two split pairs for q = D ( e ) = D ( f ) q = D(e) = D(f) q = D ( e ) = D ( f ) belong to Q y Q_y Q y . Since e e e is essential to q q q , every shortest path for q q q passes through x x x , and
dist H ( s , x ) + dist H ( x , t ) = dist H ( s , t ) . \operatorname{dist}_H(s,x) + \operatorname{dist}_H(x,t) = \operatorname{dist}_H(s,t). dist H ( s , x ) + dist H ( x , t ) = dist H ( s , t ) .
Preserving the two split pairs thus preserves q q q . In particular f ∈ E ( H y ) f \in E(H_y) f ∈ E ( H y ) by essentiality. Both endpoints of f f f lie within distance r / 2 + 1 r/2 + 1 r /2 + 1 of x x x , and x y ∈ E H xy \in E_H x y ∈ E H , so
f ∈ E ( H y [ U y ] ) . (17) f \in E(H_y[U_y]). \tag*{(17)} f ∈ E ( H y [ U y ]) . (17)
Conversely, fix a pair ( y , f ) (y,f) ( y , f ) that receives charge, and let q = D ( f ) q = D(f) q = D ( f ) . Every charging incidence ( x , e ) (x,e) ( x , e ) has x ∈ N H ( y ) x \in N_H(y) x ∈ N H ( y ) and D ( e ) = q D(e) = q D ( e ) = q . Lemma 12 bounds the number of these incidences by six. Moreover, since r ≥ 6 r \ge6 r ≥ 6 ,
U y ⊆ B H ( x , r / 2 + 3 ) ⊆ B H ( x , r ) , 1 n x ≤ 1 u y . U_y \subseteq B_H(x,r/2 + 3) \subseteq B_H(x,r),\qquad\frac{1}{n_x} \le\frac{1}{u_y}. U y ⊆ B H ( x , r /2 + 3 ) ⊆ B H ( x , r ) , n x 1 ≤ u y 1 .
Consequently
T ≤ 6 ∑ y ∈ V ∗ ∣ E ( H y [ U y ] ) ∣ u y . T \le6\sum_{y\in V^*}\frac{|E(H_y[U_y])|}{u_y}. T ≤ 6 y ∈ V ∗ ∑ u y ∣ E ( H y [ U y ]) ∣ .
By Lemma 14, since r / 2 + 2 ≥ r / 2 r/2 + 2 \ge r/2 r /2 + 2 ≥ r /2 and r ≤ l r \le l r ≤ l , we have u y = Ω ( d r ) u_y = \Omega(dr) u y = Ω ( d r ) . Combining this with Equations (15) and (16) and ∑ y d y = 2 m \sum_y d_y = 2m ∑ y d y = 2 m gives
Z = O ( ∑ y ∈ V ∗ ( 1 d + d y d d u y ) ) = O ( n d + m d r ) . Z = O\left(\sum_{y\in V^*}\left(\frac{1}{d}+\frac{d_y}{d\sqrt{du_y}}\right)\right) = O\left(\frac{n}{d}+\frac{m}{d\sqrt{r}}\right). Z = O y ∈ V ∗ ∑ ( d 1 + d d u y d y ) = O ( d n + d r m ) .
Finally, m ≥ n d / 40 m \ge nd/40 m ≥ n d /40 and r ≤ d \sqrt{r} \le d r ≤ d imply
n d ≤ 40 m d 2 ≤ 40 m d r . \frac{n}{d} \le\frac{40m}{d^2} \le\frac{40m}{d\sqrt{r}}. d n ≤ d 2 40 m ≤ d r 40 m .
This proves (13) . □
Completing the good-edge and localization proofs.
Proof of Lemma 15. Choose an absolute C 0 C_0 C 0 such that Z ≤ C 0 m / ( d r ) Z \le C_0m/(d\sqrt{r}) Z ≤ C 0 m / ( d r ) in Lemma 17. Discard an edge if either endpoint contributes more than 2 C 0 / ( d r ) 2C_0/(d\sqrt{r}) 2 C 0 / ( d r ) to the sum defining Z Z Z . Each discarded edge accounts for a distinct term exceeding this threshold, so at most m / 2 m/2 m /2 edges are discarded. The remaining edges satisfy (11) with C = 2 C 0 C = 2C_0 C = 2 C 0 . □
Proof of Lemma 16. For a fixed q q q , the assertion is immediate if there are no relevant edges. Otherwise every relevant endpoint x e x_e x e belongs to π ( q ) \pi(q) π ( q ) . The subpath from their first to their last occurrence has length at most A r Ar A r , since a subpath of a shortest path is shortest. Partition its vertices into consecutive blocks of at most ⌊ r / 2 ⌋ + 1 \lfloor r/2 \rfloor+ 1 ⌊ r /2 ⌋ + 1 vertices. Each block has path diameter at most r / 2 r/2 r /2 , and there are O ( A + 1 ) O(A+1) O ( A + 1 ) blocks because r ≥ 6 r \ge6 r ≥ 6 . In every nonempty block of assigned endpoints choose one such endpoint x i x_i x i , belonging to a good edge with label q q q . If x e x_e x e lies in that block, then e ∈ Λ H ∗ ( x i , r / 2 , q ) e \in\Lambda_H^*(x_i,r/2,q) e ∈ Λ H ∗ ( x i , r /2 , q ) . Lemma 15 therefore bounds the number of these edges by C N / ( d r ) CN/(d\sqrt{r}) C N / ( d r ) for each block. Summing over the constant number of blocks proves the claim.
Greedy Clustering and Partial Set Cover
Lemma 18 (Volume-decreasing clustering). Let W ⊆ V H W \subseteq V_H W ⊆ V H and a > 0 a > 0 a > 0 . Put v x = ∣ B H ( x , a ) ∣ v_x = |B_H(x,a)| v x = ∣ B H ( x , a ) ∣ for x ∈ W x \in W x ∈ W . There are centers C ⊆ W C \subseteq W C ⊆ W and a partition W = ⋃ c ∈ C W c W = \bigcup_{c\in C} W_c W = ⋃ c ∈ C W c such that
W c ⊆ B H ( c , 2 a ) , v x ≤ v c ( x ∈ W c ) , ∑ c ∈ C v c ≤ n , ∑ c ∈ C ∣ W c ∣ = ∣ W ∣ ≤ n . W_c \subseteq B_H(c,2a), \qquad v_x \leq v_c\ (x \in W_c), \qquad\sum_{c\in C} v_c \leq n, \qquad\sum_{c\in C} |W_c| = |W| \leq n. W c ⊆ B H ( c , 2 a ) , v x ≤ v c ( x ∈ W c ) , c ∈ C ∑ v c ≤ n , c ∈ C ∑ ∣ W c ∣ = ∣ W ∣ ≤ n .
Proof. Process W W W in nonincreasing order of v x v_x v x , breaking ties arbitrarily. Make x x x a new center if its distance from every existing center is greater than 2 a 2a 2 a ; otherwise assign it to any existing center at distance at most 2 a 2a 2 a . A center belongs to its own cluster. Each assigned center was processed earlier, giving v x ≤ v c v_x \leq v_c v x ≤ v c . Distinct centers have distance greater than 2 a 2a 2 a , so their radius-a a a balls are disjoint. The two summation bounds follow.
Lemma 19 (Partial set cover). Let { A i : i ∈ I } \{A_i : i \in I\} { A i : i ∈ I } be an indexed family of finite sets, let M = ∣ I ∣ ≥ 1 M = |I| \geq1 M = ∣ I ∣ ≥ 1 , and put
Δ = ∑ i ∈ I ∣ A i ∣ > 0 , μ ( q ) = ∣ { i : q ∈ A i } ∣ . \Delta= \sum_{i\in I} |A_i| > 0, \qquad\mu(q) = |\{i : q \in A_i\}|. Δ = i ∈ I ∑ ∣ A i ∣ > 0 , μ ( q ) = ∣ { i : q ∈ A i } ∣.
If μ ( q ) ≤ γ \mu(q) \leq\gamma μ ( q ) ≤ γ for every element q q q , there are J ⊆ I J \subseteq I J ⊆ I and Q = ⋃ i ∈ J A i Q = \bigcup_{i\in J} A_i Q = ⋃ i ∈ J A i such that
∣ Q ∣ ≥ Δ 2 γ , ∣ J ∣ ≤ 2 M Δ ∣ Q ∣ . (18) |Q| \geq\frac{\Delta}{2\gamma}, \qquad|J| \leq\frac{2M}{\Delta}|Q|. \tag*{(18)} ∣ Q ∣ ≥ 2 γ Δ , ∣ J ∣ ≤ Δ 2 M ∣ Q ∣. (18)
Proof. Starting with no covered elements, repeatedly choose a set adding at least Δ / ( 2 M ) \Delta/(2M) Δ/ ( 2 M ) new elements, until no such set exists. Each chosen set adds at least that many new elements, proving the second inequality. At termination every unchosen set contains fewer than Δ / ( 2 M ) \Delta/(2M) Δ/ ( 2 M ) uncovered elements, and every chosen set contains none. Hence
∑ i ∈ I ∣ A i ∖ Q ∣ ≤ Δ / 2 , ∑ i ∈ I ∣ A i ∩ Q ∣ ≥ Δ / 2. \sum_{i\in I} |A_i \setminus Q| \leq\Delta/2, \qquad\sum_{i\in I} |A_i \cap Q| \geq\Delta/2. i ∈ I ∑ ∣ A i ∖ Q ∣ ≤ Δ/2 , i ∈ I ∑ ∣ A i ∩ Q ∣ ≥ Δ/2.
The latter sum is ∑ q ∈ Q μ ( q ) ≤ γ ∣ Q ∣ \sum_{q\in Q} \mu(q) \leq\gamma|Q| ∑ q ∈ Q μ ( q ) ≤ γ ∣ Q ∣ , proving the first inequality. Notice that the required multiplicity assumption is an upper bound, μ ( q ) ≤ γ \mu(q) \leq\gamma μ ( q ) ≤ γ .
Proof of Lemma 10
Proof. Construct the loyal core by Lemma 13. Take the good loyal edges Λ H ′ \Lambda'_H Λ H ′ from Lemma 15. Apply Lemma 18 to W = V ∗ W = V^* W = V ∗ with a = r a = r a = r and v x = n x = ∣ B H ( x , r ) ∣ v_x = n_x = |B_H(x,r)| v x = n x = ∣ B H ( x , r ) ∣ . Denote the resulting vertex clusters by V c V_c V c . Assign every good edge e = { x , y } e = \{x,y\} e = { x , y } to one endpoint x e x_e x e of maximum radius-r r r ball volume n x e n_{x_e} n x e , breaking ties arbitrarily. Put e e e in E c E_c E c if x e ∈ V c x_e \in V_c x e ∈ V c . Thus
Λ H ′ = ⋃ c ∈ C E c , ∑ c ∣ E c ∣ = ∣ Λ H ′ ∣ = Ω ( n d ) , ∑ c ( n c + ∣ V c ∣ ) ≤ 2 n . \Lambda'_H = \bigcup_{c\in C} E_c, \qquad\sum_c |E_c| = |\Lambda'_H| = \Omega(nd), \qquad\sum_c (n_c + |V_c|) \leq2n. Λ H ′ = c ∈ C ⋃ E c , c ∑ ∣ E c ∣ = ∣ Λ H ′ ∣ = Ω ( n d ) , c ∑ ( n c + ∣ V c ∣ ) ≤ 2 n .
By averaging, some center c c c satisfies
∣ E c ∣ = Ω ( d ( n c + ∣ V c ∣ ) ) . (19) |E_c| = \Omega\bigl(d(n_c + |V_c|)\bigr). \tag*{(19)} ∣ E c ∣ = Ω ( d ( n c + ∣ V c ∣ ) ) . (19)
Fix this center. Its assigned endpoints lie in V c ⊆ B H ( c , 2 r ) V_c \subseteq B_H(c,2r) V c ⊆ B H ( c , 2 r ) , have diameter at most 4 r 4r 4 r , and satisfy n x e ≤ n c n_{x_e} \le n_c n x e ≤ n c . Lemma 16 yields
γ c : = max q ∈ R ∣ { e ∈ E c : D ( e ) = q } ∣ = O ( n c d r ) . (20) \gamma_c := \max_{q \in R} \lvert\{e \in E_c : D(e)=q\}\rvert= O\left(\frac{n_c}{d\sqrt{r}}\right). \tag*{(20)} γ c := q ∈ R max ∣{ e ∈ E c : D ( e ) = q }∣ = O ( d r n c ) . (20)
For every x ∈ V c x \in V_c x ∈ V c define the set
A x = { q : some e ∈ E c has x ∈ e and D ( e ) = q } . A_x = \{q : \text{some } e \in E_c \text{ has } x \in e \text{ and } D(e)=q\}. A x = { q : some e ∈ E c has x ∈ e and D ( e ) = q } .
Only edges of E c E_c E c are used in these sets. Set M = ∣ V c ∣ M = \lvert V_c\rvert M = ∣ V c ∣ and Δ = ∑ x ∈ V c ∣ A x ∣ \Delta= \sum_{x \in V_c}\lvert A_x\rvert Δ = ∑ x ∈ V c ∣ A x ∣ . Count the incidences ( x , e ) (x,e) ( x , e ) with x ∈ V c x \in V_c x ∈ V c , e ∈ E c e \in E_c e ∈ E c , and x ∈ e x \in e x ∈ e . Each edge contributes at least one incidence, through its assigned endpoint, and at most two. Each vertex-label pair ( x , q ) (x,q) ( x , q ) accounts for at most two incidences by Lemma 12 . Therefore
∣ E c ∣ / 2 ≤ Δ ≤ 2 ∣ E c ∣ . (21) \lvert E_c\rvert/2 \le\Delta\le2\lvert E_c\rvert. \tag*{(21)} ∣ E c ∣ /2 ≤ Δ ≤ 2 ∣ E c ∣ . (21)
Moreover the multiplicity of any q q q among the A x A_x A x is at most 2 ∣ { e ∈ E c : D ( e ) = q } ∣ ≤ 2 γ c 2\lvert\{e \in E_c : D(e)=q\}\rvert\le2\gamma_c 2 ∣{ e ∈ E c : D ( e ) = q }∣ ≤ 2 γ c .
Apply Lemma 19 with γ = 2 γ c \gamma=2\gamma_c γ = 2 γ c . It returns S ⊆ V c S \subseteq V_c S ⊆ V c and Q = ⋃ x ∈ S A x Q = \bigcup_{x \in S} A_x Q = ⋃ x ∈ S A x satisfying
∣ Q ∣ ≥ Δ 4 γ c = Ω ( ∣ E c ∣ γ c ) = Ω ( d n c n c / ( d r ) ) = Ω ( d 2 r ) , \lvert Q\rvert\ge\frac{\Delta}{4\gamma_c} = \Omega\left(\frac{\lvert E_c\rvert}{\gamma_c}\right) = \Omega\left(\frac{d n_c}{n_c/(d\sqrt{r})}\right) = \Omega(d^2\sqrt{r}), ∣ Q ∣ ≥ 4 γ c Δ = Ω ( γ c ∣ E c ∣ ) = Ω ( n c / ( d r ) d n c ) = Ω ( d 2 r ) ,
∣ S ∣ ≤ 2 ∣ V c ∣ Δ ∣ Q ∣ = O ( ∣ V c ∣ ∣ E c ∣ ∣ Q ∣ ) = O ( ∣ Q ∣ / d ) . \lvert S\rvert\le\frac{2\lvert V_c\rvert}{\Delta}\lvert Q\rvert= O\left(\frac{\lvert V_c\rvert}{\lvert E_c\rvert}\lvert Q\rvert\right) = O(\lvert Q\rvert/d). ∣ S ∣ ≤ Δ 2 ∣ V c ∣ ∣ Q ∣ = O ( ∣ E c ∣ ∣ V c ∣ ∣ Q ∣ ) = O (∣ Q ∣ / d ) .
Here we used Equations (19) to (21) . Every membership q ∈ A x q \in A_x q ∈ A x witnesses that x x x covers q q q , so S S S covers Q Q Q . Finally, S ⊆ B H ( c , 2 r ) S \subseteq B_H(c,2r) S ⊆ B H ( c , 2 r ) gives diam H ( S ) ≤ 4 r \operatorname{diam}_H(S) \le4r diam H ( S ) ≤ 4 r .
Proof of the hitting lemma
Proof. Assume r ≥ 6 r \ge6 r ≥ 6 and let Λ H ′ \Lambda'_H Λ H ′ be the same good-edge set as in Lemma 15 .
Selecting hitting tuples. Set k = ⌈ d / 40 ⌉ = Θ ( d ) k = \lceil d/40\rceil= \Theta(d) k = ⌈ d /40 ⌉ = Θ ( d ) . For every rich vertex x x x , pick an arbitrary set A ( x ) ⊆ N H L ( x ) A(x) \subseteq N_{HL}(x) A ( x ) ⊆ N H L ( x ) of exactly k k k loyal neighbors. Set up
T = { ( u , x , e ) : e ∈ Λ H ′ , x ∈ e , u ∈ A ( x ) } . \mathcal{T} = \{(u,x,e) : e \in\Lambda'_H,\ x \in e,\ u \in A(x)\}. T = {( u , x , e ) : e ∈ Λ H ′ , x ∈ e , u ∈ A ( x )} .
Every tuple witnesses that u u u hits D ( e ) D(e) D ( e ) . Because both endpoints of each good edge are rich,
∣ T ∣ = 2 k ∣ Λ H ′ ∣ = Ω ( n d 2 ) . (22) \lvert\mathcal{T}\rvert= 2k\lvert\Lambda'_H\rvert= \Omega(nd^2). \tag*{(22)} ∣ T ∣ = 2 k ∣ Λ H ′ ∣ = Ω ( n d 2 ) . (22)
For a fixed pair ( u , q ) (u,q) ( u , q ) , by Lemma 12 , at most six tuples have first coordinate u u u and edge label q q q .
Clustering the hitting vertices. Define
W = { u : ( u , x , e ) ∈ T for some x , e } , N u = ∣ B H ( u , 2 r ) ∣ ( u ∈ W ) . W = \{u : (u,x,e) \in\mathcal{T}\text{ for some }x,e\}, \qquad N_u = \lvert B_H(u,2r)\rvert\quad(u \in W). W = { u : ( u , x , e ) ∈ T for some x , e } , N u = ∣ B H ( u , 2 r )∣ ( u ∈ W ) .
Apply Lemma 18 to W W W with radius a = 2 r a=2r a = 2 r . Write V c V_c V c for its clusters, so that
V c ⊆ B H ( c , 4 r ) , N u ≤ N c ( u ∈ V c ) , ∑ c ( N c + ∣ V c ∣ ) ≤ 2 n . V_c \subseteq B_H(c,4r), \qquad N_u \le N_c \ (u \in V_c), \qquad\sum_c(N_c+\lvert V_c\rvert) \le2n. V c ⊆ B H ( c , 4 r ) , N u ≤ N c ( u ∈ V c ) , c ∑ ( N c + ∣ V c ∣) ≤ 2 n .
Assign each tuple to the cluster of its first coordinate: T c = { ( u , x , e ) ∈ T : u ∈ V c } \mathcal{T}_c = \{(u,x,e) \in\mathcal{T} : u \in V_c\} T c = {( u , x , e ) ∈ T : u ∈ V c } . By Equation (22) and weighted averaging, some center c c c satisfies
∣ T c ∣ = Ω ( d 2 ( N c + ∣ V c ∣ ) ) . (23) \lvert\mathcal{T}_c\rvert= \Omega\left(d^2(N_c+\lvert V_c\rvert)\right). \tag*{(23)} ∣ T c ∣ = Ω ( d 2 ( N c + ∣ V c ∣) ) . (23)
Fix this center c c c for the rest of the proof. Bounding repetitions of a demand. Let F c F_c F c be the set of distinct edges appearing in T c \mathcal{T}_c T c . For each e ∈ F c e \in F_c e ∈ F c choose one witnessing tuple ( u e , x e , e ) (u_e, x_e, e) ( u e , x e , e ) . Since u e ∈ V c u_e \in V_c u e ∈ V c and u e x e ∈ E H u_ex_e \in E_H u e x e ∈ E H ,
x e ∈ B H ( c , 4 r + 1 ) , B H ( x e , r ) ⊆ B H ( u e , r + 1 ) ⊆ B H ( u e , 2 r ) . x_e \in B_H(c,4r+1), \qquad B_H(x_e,r) \subseteq B_H(u_e,r+1) \subseteq B_H(u_e,2r). x e ∈ B H ( c , 4 r + 1 ) , B H ( x e , r ) ⊆ B H ( u e , r + 1 ) ⊆ B H ( u e , 2 r ) .
Consequently n x e ≤ N u e ≤ N c n_{x_e} \leq N_{u_e} \leq N_c n x e ≤ N u e ≤ N c , and the assigned endpoints have diameter at most 8 r + 2 ≤ 9 r 8r+2 \leq9r 8 r + 2 ≤ 9 r . Apply Lemma 16 to F c F_c F c . Therefore, for every q q q ,
∣ { e ∈ F c : D ( e ) = q } ∣ = O ( N c d r ) . \left|\{e \in F_c : D(e) = q\}\right| = O\left(\frac{N_c}{d\sqrt{r}}\right). ∣ { e ∈ F c : D ( e ) = q } ∣ = O ( d r N c ) .
Each distinct edge contributes at most 2 k = O ( d ) 2k = O(d) 2 k = O ( d ) selected tuples. It follows that
∣ { ( u , x , e ) ∈ T c : D ( e ) = q } ∣ = O ( N c r ) . (24) \left|\{(u,x,e) \in\mathcal{T}_c : D(e) = q\}\right| = O\left(\frac{N_c}{\sqrt{r}}\right). \tag*{(24)} ∣ {( u , x , e ) ∈ T c : D ( e ) = q } ∣ = O ( r N c ) . (24)
Partial set cover. For each u ∈ V c u \in V_c u ∈ V c , define A u = { q : there is a tuple ( u , x , e ) ∈ T c with D ( e ) = q } A_u = \{q : \text{there is a tuple } (u,x,e) \in\mathcal{T}_c \text{ with } D(e) = q\} A u = { q : there is a tuple ( u , x , e ) ∈ T c with D ( e ) = q } . Put M = ∣ V c ∣ M = |V_c| M = ∣ V c ∣ and Δ = ∑ u ∈ V c ∣ A u ∣ \Delta= \sum_{u\in V_c}|A_u| Δ = ∑ u ∈ V c ∣ A u ∣ . Each incidence ( u , q ) (u,q) ( u , q ) is witnessed by at least one and at most six tuples, hence
∣ T c ∣ / 6 ≤ Δ ≤ ∣ T c ∣ . (25) |\mathcal{T}_c|/6 \leq\Delta\leq|\mathcal{T}_c|. \tag*{(25)} ∣ T c ∣/6 ≤ Δ ≤ ∣ T c ∣. (25)
By Equation (24) , each demand occurs in at most γ = O ( N c / r ) \gamma= O(N_c/\sqrt{r}) γ = O ( N c / r ) of the sets A u A_u A u . Applying Lemma 19 gives S ⊆ V c S \subseteq V_c S ⊆ V c and Q = ⋃ u ∈ S A u Q = \bigcup_{u\in S} A_u Q = ⋃ u ∈ S A u with
∣ Q ∣ ≥ Δ 2 γ = Ω ( ∣ T c ∣ N c / r ) = Ω ( d 2 r ) , |Q| \geq\frac{\Delta}{2\gamma} = \Omega\left(\frac{|\mathcal{T}_c|}{N_c/\sqrt{r}}\right) = \Omega(d^2\sqrt{r}), ∣ Q ∣ ≥ 2 γ Δ = Ω ( N c / r ∣ T c ∣ ) = Ω ( d 2 r ) ,
∣ S ∣ ≤ 2 ∣ V c ∣ Δ ∣ Q ∣ = O ( ∣ V c ∣ ∣ T c ∣ ∣ Q ∣ ) = O ( ∣ Q ∣ / d 2 ) , |S| \leq\frac{2|V_c|}{\Delta}|Q| = O\left(\frac{|V_c|}{|\mathcal{T}_c|}|Q|\right) = O(|Q|/d^2), ∣ S ∣ ≤ Δ 2∣ V c ∣ ∣ Q ∣ = O ( ∣ T c ∣ ∣ V c ∣ ∣ Q ∣ ) = O ( ∣ Q ∣/ d 2 ) ,
using Equation (23) and Equation (25) . By the definition of A u A_u A u , the set S S S hits Q Q Q . Finally, S ⊆ B H ( c , 4 r ) S \subseteq B_H(c,4r) S ⊆ B H ( c , 4 r ) implies diam H ( S ) ≤ 8 r \operatorname{diam}_H(S) \leq8r diam H ( S ) ≤ 8 r .
Proof of Theorem 1
In this section, we use Lemma 10 in an iterative demand-removal procedure to prove Theorem 1 .
There are two types of deletion. A demand with few private edges can be removed at small edge cost. Once no such demand remains, private lengths are large, and their sum guarantees enough private edges to apply Lemma 10 . Its covered batch has a small distance preserver, which bounds the edge loss when the batch is removed. We continue until at most half the demands remain, while retaining at least three quarters of the original edges. The induction hypothesis then gives a contradiction.
We prove the following stronger statement: there is an absolute constant C C C such that, for every n n n -vertex graph G G G and every demand set P P P with n 1 / 4 ≤ p : = ∣ P ∣ ≤ n n^{1/4} \leq p := |P| \leq n n 1/4 ≤ p := ∣ P ∣ ≤ n , every minimal distance preserver H = ( V H , E H ) H = (V_H,E_H) H = ( V H , E H ) of ( G , P ) (G,P) ( G , P ) satisfies
∣ E H ∣ ≤ C n 8 / 9 p 4 / 9 . (26) |E_H| \leq Cn^{8/9}p^{4/9}. \tag*{(26)} ∣ E H ∣ ≤ C n 8/9 p 4/9 . (26)
This implies Theorem 1 in its stated range n 1 / 2 ≤ p ≤ n n^{1/2} \leq p \leq n n 1/2 ≤ p ≤ n . We retain all n n n vertices in every subgraph, including isolated vertices. Trivial demands and demands between different connected components may be discarded without changing which subgraphs preserve the demands or which preservers are minimal. If fewer than n 1 / 4 n^{1/4} n 1/4 nontrivial reachable demands remain, Lemma 2 gives O ( n ) O(n) O ( n ) edges, within the claimed bound for the original p ≥ n 1 / 4 p \geq n^{1/4} p ≥ n 1/4 . Otherwise we prove the statement for the remaining demands, and the original bound follows by monotonicity in p p p .
Edge Removal Under Demand Deletion
We first discuss how removing demands affects a minimal distance preserver.
Observation 20 (Removing one demand). Let K K K be a minimal distance preserver of ( K , R ) (K,R) ( K , R ) , let q ∈ R q \in R q ∈ R , and put R ′ = R ∖ { q } R' = R \setminus\{q\} R ′ = R ∖ { q } . Every distance preserver K ′ ⊆ K K' \subseteq K K ′ ⊆ K of ( K , R ′ ) (K,R') ( K , R ′ ) contains every edge e ∈ E ( K ) e \in E(K) e ∈ E ( K ) for which D K R ( e ) ≠ { q } D^{R}_{K}(e) \ne\{q\} D K R ( e ) = { q } . Consequently,
∣ E ( K ) ∣ − ∣ E ( K ′ ) ∣ ≤ λ K ( q ) . (27) |E(K)| - |E(K')| \le\lambda_K(q). \tag*{(27)} ∣ E ( K ) ∣ − ∣ E ( K ′ ) ∣ ≤ λ K ( q ) . (27) Here λ K ( q ) \lambda_K(q) λ K ( q ) is the private length before q q q is removed.
Proof. Minimality gives D K R ( e ) ≠ ∅ D^{R}_{K}(e) \ne\varnothing D K R ( e ) = ∅ for every e ∈ E ( K ) e \in E(K) e ∈ E ( K ) . If D K R ( e ) ≠ { q } D^{R}_{K}(e) \ne\{q\} D K R ( e ) = { q } , choose a demand q ′ ∈ D K R ( e ) ∖ { q } q' \in D^{R}_{K}(e) \setminus\{q\} q ′ ∈ D K R ( e ) ∖ { q } . Every shortest path for q ′ q' q ′ in K K K contains e e e . Since K ′ K' K ′ preserves q ′ q' q ′ , it contains such a path and hence contains e e e . Therefore, only edges in Λ K ( q ) \Lambda_K(q) Λ K ( q ) can be removed.
Lemma 21 (Removing a covered demand set). Let K K K be a minimal distance preserver of ( K , R ) (K,R) ( K , R ) , with at most n n n vertices. Suppose that a nonempty set S ⊆ V ( K ) S \subseteq V(K) S ⊆ V ( K ) covers a nonempty demand set Q ⊆ R Q \subseteq R Q ⊆ R , and diam K ( S ) < ∞ \operatorname{diam}_K(S) < \infty diam K ( S ) < ∞ . There is a distance preserver H ( Q ) ⊆ K H(Q) \subseteq K H ( Q ) ⊆ K of ( K , Q ) (K,Q) ( K , Q ) such that, for every distance preserver K ′ ⊆ K K' \subseteq K K ′ ⊆ K of ( K , R ∖ Q ) (K,R \setminus Q) ( K , R ∖ Q ) ,
∣ E ( K ) ∣ − ∣ E ( K ′ ) ∣ ≤ ∣ E ( H ( Q ) ) ∣ ≤ A ( n + n ∣ Q ∣ ∣ S ∣ diam K ( S ) ) , (28) |E(K)| - |E(K')| \le|E(H(Q))| \le A\left(n + \sqrt{n|Q||S|\operatorname{diam}_K(S)}\right), \tag*{(28)} ∣ E ( K ) ∣ − ∣ E ( K ′ ) ∣ ≤ ∣ E ( H ( Q )) ∣ ≤ A ( n + n ∣ Q ∣∣ S ∣ diam K ( S ) ) , (28) where A A A is an absolute constant.
Proof. For each q = ( s , t ) ∈ Q q=(s,t) \in Q q = ( s , t ) ∈ Q , choose a covering vertex u q ∈ S u_q \in S u q ∈ S . By Definition 8 , it is incident to an edge essential to q q q , so it belongs to every shortest path for q q q in K K K . Hence
dist K ( s , u q ) + dist K ( u q , t ) = dist K ( s , t ) . (29) \operatorname{dist}_K(s,u_q) + \operatorname{dist}_K(u_q,t) = \operatorname{dist}_K(s,t). \tag*{(29)} dist K ( s , u q ) + dist K ( u q , t ) = dist K ( s , t ) . (29) Form the split demand set
Q ∗ = ⋃ q = ( s , t ) ∈ Q { ( u q , s ) , ( u q , t ) } ⊆ S × V ( K ) , Q^* = \bigcup_{q=(s,t)\in Q}\{(u_q,s),(u_q,t)\} \subseteq S \times V(K), Q ∗ = q = ( s , t ) ∈ Q ⋃ {( u q , s ) , ( u q , t )} ⊆ S × V ( K ) , omitting repeated and trivial pairs. Thus ∣ Q ∗ ∣ ≤ 2 ∣ Q ∣ |Q^*| \le2|Q| ∣ Q ∗ ∣ ≤ 2∣ Q ∣ . If ∣ S ∣ = 1 |S| = 1 ∣ S ∣ = 1 , choose a BFS tree rooted at its unique vertex, then a minimal subgraph of that tree preserving Q ∗ Q^* Q ∗ . Otherwise choose a minimal distance preserver of ( K , Q ∗ ) (K,Q^*) ( K , Q ∗ ) and apply Lemma 4 . In either case, call the resulting subgraph H ( Q ) H(Q) H ( Q ) . It satisfies
∣ E ( H ( Q ) ) ∣ = O ( n + n ∣ Q ∣ ∣ S ∣ diam K ( S ) ) . |E(H(Q))| = O\left(n + \sqrt{n|Q||S|\operatorname{diam}_K(S)}\right). ∣ E ( H ( Q )) ∣ = O ( n + n ∣ Q ∣∣ S ∣ diam K ( S ) ) . The two preserved routes in Equation (29) show that H ( Q ) H(Q) H ( Q ) is also a distance preserver of ( K , Q ) (K,Q) ( K , Q ) . For any remaining-demand preserver K ′ K' K ′ , the subgraph K ′ ∪ H ( Q ) K' \cup H(Q) K ′ ∪ H ( Q ) preserves all demands in R R R exactly. Minimality of K K K therefore gives
E ( K ′ ) ∪ E ( H ( Q ) ) = E ( K ) . (30) E(K') \cup E(H(Q)) = E(K). \tag*{(30)} E ( K ′ ) ∪ E ( H ( Q )) = E ( K ) . (30) Indeed, a missing edge would be essential to some demand in R R R , contradicting preservation of that demand. Thus E ( K ) ∖ E ( K ′ ) ⊆ E ( H ( Q ) ) E(K) \setminus E(K') \subseteq E(H(Q)) E ( K ) ∖ E ( K ′ ) ⊆ E ( H ( Q )) , proving Equation (28) after fixing A A A sufficiently large.
Induction and Fixed Parameters
Let C C E C_{\mathrm{CE}} C CE be an absolute constant such that, by Lemma 2 , every minimal distance preserver J J J of an n n n -vertex graph with demand set T T T has size
∣ E ( J ) ∣ ≤ C C E ( n + n 1 / 2 ∣ T ∣ ) . (31) |E(J)| \le C_{\mathrm{CE}}(n+n^{1/2}|T|). \tag*{(31)} ∣ E ( J ) ∣ ≤ C CE ( n + n 1/2 ∣ T ∣ ) . (31)
We prove Equation (26) by strong induction on the integer p p p , uniformly over all n n n -vertex graphs and demand sets of size p p p in [ n 1 / 4 , n ] [n^{1/4},n] [ n 1/4 , n ] .
Base Case Consider the range n 1 / 4 ≤ p ≤ n 7 / 10 n^{1/4} \le p \le n^{7/10} n 1/4 ≤ p ≤ n 7/10 . It satisfies that n ≤ n 8 / 9 p 4 / 9 n \le n^{8/9}p^{4/9} n ≤ n 8/9 p 4/9 and n 1 / 2 p ≤ n 8 / 9 p 4 / 9 n^{1/2}p \le n^{8/9}p^{4/9} n 1/2 p ≤ n 8/9 p 4/9 . By Equation (31) with C ≥ 2 C C E C \ge2C_{\mathrm{CE}} C ≥ 2 C CE , every minimal distance preserver H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) of ( G , P ) (G,P) ( G , P ) has size
∣ E H ∣ ≤ C C E ( n + n 1 / 2 p ) ≤ C n 8 / 9 p 4 / 9 . |E_H| \le C_{\mathrm{CE}}(n+n^{1/2}p) \le Cn^{8/9}p^{4/9}. ∣ E H ∣ ≤ C CE ( n + n 1/2 p ) ≤ C n 8/9 p 4/9 .
Inductive Step Consider the range n 7 / 10 < p ≤ n n^{7/10}<p\le n n 7/10 < p ≤ n . Assume the inductive statement for all smaller integer demand counts in [ n 1 / 4 , p − 1 ] [n^{1/4},p-1] [ n 1/4 , p − 1 ] . We need the following result for small residual sets.
Claim 22. Under the induction hypothesis, every minimal distance preserver J J J of ( G , R ) (G,R) ( G , R ) with ∣ R ∣ ≤ p / 2 |R|\le p/2 ∣ R ∣ ≤ p /2 satisfies
∣ E ( J ) ∣ ≤ C n 8 / 9 ( p / 2 ) 4 / 9 . (32) |E(J)| \le Cn^{8/9}(p/2)^{4/9}. \tag*{(32)} ∣ E ( J ) ∣ ≤ C n 8/9 ( p /2 ) 4/9 . (32)
Proof. Set p ′ = ∣ R ∣ p'=|R| p ′ = ∣ R ∣ . Suppose p ′ ≥ n 1 / 4 p'\ge n^{1/4} p ′ ≥ n 1/4 . Given p ′ < p p'<p p ′ < p , by induction, ∣ E ( J ) ∣ ≤ C n 8 / 9 ( p ′ ) 4 / 9 ≤ C n 8 / 9 ( p / 2 ) 4 / 9 |E(J)|\le Cn^{8/9}(p')^{4/9}\le Cn^{8/9}(p/2)^{4/9} ∣ E ( J ) ∣ ≤ C n 8/9 ( p ′ ) 4/9 ≤ C n 8/9 ( p /2 ) 4/9 . Suppose p ′ < n 1 / 4 p'<n^{1/4} p ′ < n 1/4 . By Equation (31) ,
∣ E ( J ) ∣ ≤ C C E ( n + n 1 / 2 p ′ ) ≤ C C E ( n + n 3 / 4 ) ≤ 2 C C E n . |E(J)| \le C_{\mathrm{CE}}(n+n^{1/2}p')\le C_{\mathrm{CE}}(n+n^{3/4})\le2C_{\mathrm{CE}}n. ∣ E ( J ) ∣ ≤ C CE ( n + n 1/2 p ′ ) ≤ C CE ( n + n 3/4 ) ≤ 2 C CE n .
Since p ≥ n 1 / 4 p\ge n^{1/4} p ≥ n 1/4 , we have n 8 / 9 ( p / 2 ) 4 / 9 ≥ 2 − 4 / 9 n n^{8/9}(p/2)^{4/9}\ge2^{-4/9}n n 8/9 ( p /2 ) 4/9 ≥ 2 − 4/9 n . Choosing C ≥ 2 13 / 9 C C E C\ge2^{13/9}C_{\mathrm{CE}} C ≥ 2 13/9 C CE therefore gives the required bound
∣ E ( J ) ∣ ≤ 2 C C E n ≤ C n 8 / 9 ( p / 2 ) 4 / 9 . |E(J)|\le2C_{\mathrm{CE}}n\le Cn^{8/9}(p/2)^{4/9}. ∣ E ( J ) ∣ ≤ 2 C CE n ≤ C n 8/9 ( p /2 ) 4/9 .
:::
We prove the inductive step by contradiction. Suppose that a minimal distance preserver H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) of ( G , P ) (G,P) ( G , P ) violates Equation (26) . Fix
n = ∣ V H ∣ , d = ∣ E H ∣ / n , n d = ∣ E H ∣ > C n 8 / 9 p 4 / 9 . (33) n=|V_H|,\qquad d=|E_H|/n,\qquad nd=|E_H|>Cn^{8/9}p^{4/9}. \tag*{(33)} n = ∣ V H ∣ , d = ∣ E H ∣/ n , n d = ∣ E H ∣ > C n 8/9 p 4/9 . (33)
The average degree of H H H is 2 d 2d 2 d . In addition, we define
ℓ = n d 5 p , r 0 = n 1 / 2 d − 3 / 2 , r = max { 6 , r 0 } . (34) \ell=\frac{nd}{5p},\qquad r_0=n^{1/2}d^{-3/2},\qquad r=\max\{6,r_0\}. \tag*{(34)} ℓ = 5 p n d , r 0 = n 1/2 d − 3/2 , r = max { 6 , r 0 } . (34)
All five parameters n , d , p , ℓ , r n,d,p,\ell,r n , d , p , ℓ , r remain fixed throughout the procedure.
Demand Removal Procedure
The residual graph and its update. At every stage, we use R ⊆ P R \subseteq P R ⊆ P to denote the demands still present. Let H ( R ) ⊆ H H(R) \subseteq H H ( R ) ⊆ H be the current minimal distance preserver of ( G , R ) (G,R) ( G , R ) . If the demand set changes from R R R to R ′ ⊆ R R' \subseteq R R ′ ⊆ R , pick an arbitrary minimal subgraph H ( R ′ ) H(R') H ( R ′ ) of the current H ( R ) H(R) H ( R ) that preserves all the demands in R ′ R' R ′ .
Note that such an update exists: repeatedly remove one edge from H ( R ) H(R) H ( R ) whose removal preserves the demands in R ′ R' R ′ , recomputing essentiality after each deletion, until no further deletion is possible. If K = H ( R ) K=H(R) K = H ( R ) is the graph just before the update and K ′ = H ( R ′ ) K'=H(R') K ′ = H ( R ′ ) the graph after it, then for every q ∈ R ′ q \in R' q ∈ R ′ ,
dist K ′ ( q ) = dist K ( q ) = dist H ( q ) = dist G ( q ) . \operatorname{dist}_{K'}(q)=\operatorname{dist}_{K}(q)=\operatorname{dist}_{H}(q)=\operatorname{dist}_{G}(q). dist K ′ ( q ) = dist K ( q ) = dist H ( q ) = dist G ( q ) .
Here dist K ( q ) \operatorname{dist}_{K}(q) dist K ( q ) denotes the distance between the endpoints of q q q . Thus K ′ K' K ′ is a minimal distance preserver of ( G , R ′ ) (G,R') ( G , R ′ ) as well as of ( K , R ′ ) (K,R') ( K , R ′ ) . Essentiality and private lengths are recomputed in each updated instance.
Demand-removal procedure. Set R = P R=P R = P and H ( R ) = H H(R)=H H ( R ) = H as the initialization. Repeat the following two steps while ∣ R ∣ > p / 2 |R|>p/2 ∣ R ∣ > p /2 .
Remove demands of small private length. While ∣ R ∣ > p / 2 |R|>p/2 ∣ R ∣ > p /2 and there exists a demand q ∈ R q \in R q ∈ R with λ H ( R ) ( q ) ≤ l \lambda_{H(R)}(q) \le l λ H ( R ) ( q ) ≤ l , remove q q q from R R R , update H ( R ) H(R) H ( R ) and recompute the private lengths. If ∣ R ∣ ≤ p / 2 |R| \le p/2 ∣ R ∣ ≤ p /2 , terminate the procedure.
Remove a covered batch. Now ∣ R ∣ > p / 2 |R|>p/2 ∣ R ∣ > p /2 and λ H ( R ) ( q ) > l \lambda_{H(R)}(q)>l λ H ( R ) ( q ) > l for every q ∈ R q \in R q ∈ R . The private-edge sets of different demands are disjoint, so
∣ Λ H ( R ) ∣ = ∑ q ∈ R λ H ( R ) ( q ) > ∣ R ∣ l > p 2 n d 5 p = n d 10 . (35) |\Lambda_{H(R)}|=\sum_{q\in R}\lambda_{H(R)}(q)>|R|l>\frac{p}{2}\frac{nd}{5p}=\frac{nd}{10}. \tag*{(35)} ∣ Λ H ( R ) ∣ = q ∈ R ∑ λ H ( R ) ( q ) > ∣ R ∣ l > 2 p 5 p n d = 10 n d . (35)
Apply Lemma 10 to the current graph K = H ( R ) K=H(R) K = H ( R ) , with the fixed parameters n , d , l , r n,d,l,r n , d , l , r defined in Equation (34) and verified in Lemma 24 . We obtain nonempty sets Q ⊆ R Q \subseteq R Q ⊆ R and S ⊆ V H S \subseteq V_H S ⊆ V H such that S S S covers Q Q Q in K K K , and
∣ Q ∣ ≥ c 0 d r , ∣ S ∣ ≤ c 1 ∣ Q ∣ / d , diam K ( S ) ≤ c 2 r , (36) |Q|\ge c_0d^r,\qquad|S|\le c_1|Q|/d,\qquad\operatorname{diam}_K(S)\le c_2r, \tag*{(36)} ∣ Q ∣ ≥ c 0 d r , ∣ S ∣ ≤ c 1 ∣ Q ∣/ d , diam K ( S ) ≤ c 2 r , (36)
where c 0 > 0 , c 1 , c 2 c_0>0,c_1,c_2 c 0 > 0 , c 1 , c 2 are absolute constants from Lemma 10 . Remove Q Q Q from R R R and update H ( R ) H(R) H ( R ) to a minimal subgraph preserving all remaining distances.
Each pass removes at least one demand, and no demand is reintroduced, so the procedure terminates with ∣ R ∣ ≤ p / 2 |R|\le p/2 ∣ R ∣ ≤ p /2 . All hypotheses of Lemma 10 hold in the current instance: H ( R ) H(R) H ( R ) is a minimal distance preserver of ( G , R ) (G,R) ( G , R ) , retains n n n vertices, and has at most n d nd n d edges by containment in H H H . Equation (35) gives the required private-edge mass, and every active demand has private length greater than l l l . The radius condition is checked below; the diameter conclusion is measured in the current graph H ( R ) H(R) H ( R ) itself.
Lemma 23 (Total loss in Step 1). The total number of edges removed in Step 1 is at most n d / 5 nd/5 n d /5 .
Proof. Immediately before a single demand q q q is removed in Step 1, its private length is at most l l l . Observation 20 , applied to that current graph and demand set, bounds the number of edges lost in the update by l l l . There are at most p p p such removals. The total is therefore at most p l = n d / 5 pl=nd/5 pl = n d /5 .
Lemma 24. For sufficiently large C C C , the parameters in Equation (34) satisfy 6 ≤ r ≤ min { d 2 , l } 6 \le r \le\min\{d^2,l\} 6 ≤ r ≤ min { d 2 , l } . In each execution of Step 2, removing its demand set Q Q Q and then updating the graph deletes at most
C 2 ( n + ∣ Q ∣ n r d ) (37) C_2\left(n+|Q|\sqrt{\frac{nr}{d}}\right) \tag*{(37)} C 2 ( n + ∣ Q ∣ d n r ) (37) edges for an absolute constant C 2 C_2 C 2 independent of C C C .
Proof. Since p > n 7 / 10 p > n^{7/10} p > n 7/10 , Equation (33) implies d > C n − 1 / 9 p 4 / 9 > C n 1 / 5 ≥ C d > Cn^{-1/9}p^{4/9} > Cn^{1/5} \ge C d > C n − 1/9 p 4/9 > C n 1/5 ≥ C . Therefore
r 0 d = n 1 / 2 d 5 / 2 < C − 5 / 2 , l = n d 5 p ≥ d 5 . \frac{r_0}{d}=\frac{n^{1/2}}{d^{5/2}}<C^{-5/2},\qquad l=\frac{nd}{5p}\ge\frac{d}{5}. d r 0 = d 5/2 n 1/2 < C − 5/2 , l = 5 p n d ≥ 5 d .
If C ≥ 30 C \ge30 C ≥ 30 , then d > C ≥ 30 d > C \ge30 d > C ≥ 30 , so 6 ≤ d / 5 6 \le d/5 6 ≤ d /5 . Also C − 5 / 2 ≤ 1 / 5 C^{-5/2} \le1/5 C − 5/2 ≤ 1/5 , hence r 0 ≤ d / 5 r_0 \le d/5 r 0 ≤ d /5 . Therefore
6 ≤ r = max { 6 , r 0 } ≤ d / 5 ≤ min { d 2 , l } , 6 \le r=\max\{6,r_0\}\le d/5\le\min\{d^2,l\}, 6 ≤ r = max { 6 , r 0 } ≤ d /5 ≤ min { d 2 , l } ,
which verifies the radius condition of Lemma 10 .
Let K = H ( R ) K=H(R) K = H ( R ) immediately before Step 2. By Lemma 21 and Eq. (36) , the number of edges deleted from K K K is at most
∣ E ( H ( Q ) ) ∣ ≤ A ( n + n ∣ Q ∣ ∣ S ∣ diam K ( S ) ) ≤ A ( n + c 1 c 2 ∣ Q ∣ n r d ) ≤ C 2 ( n + ∣ Q ∣ n r d ) . \begin{aligned}
|E(H(Q))| &\le A\left(n+\sqrt{n|Q||S|\operatorname{diam}_K(S)}\right)\\
&\le A\left(n+\sqrt{c_1c_2|Q|\frac{nr}{d}}\right)
\le C_2\left(n+|Q|\sqrt{\frac{nr}{d}}\right).
\end{aligned} ∣ E ( H ( Q )) ∣ ≤ A ( n + n ∣ Q ∣∣ S ∣ diam K ( S ) ) ≤ A ( n + c 1 c 2 ∣ Q ∣ d n r ) ≤ C 2 ( n + ∣ Q ∣ d n r ) .
:::
Lemma 25 (Total loss in Step 2). For sufficiently large C C C , the total number of edges removed in Step 2 is at most n d / 20 nd/20 n d /20 .
Proof. Let Q i , S i Q_i,S_i Q i , S i , for i = 1 , … , τ i=1,\ldots,\tau i = 1 , … , τ , be the sets selected in the executions of Step 2. These demand sets are pairwise disjoint subsets of P P P , so
∑ i = 1 τ ∣ Q i ∣ ≤ p , τ ≤ p c 0 d 2 r , \sum_{i=1}^{\tau}|Q_i|\le p,\qquad\tau\le\frac{p}{c_0d^2\sqrt{r}}, i = 1 ∑ τ ∣ Q i ∣ ≤ p , τ ≤ c 0 d 2 r p ,
by Equation (36) . Summing Equation (37) , the total loss is at most
C 1 ( n p d 2 r + p n r d ) , (38) C_1\left(\frac{np}{d^2\sqrt{r}}+p\sqrt{\frac{nr}{d}}\right), \tag*{(38)} C 1 ( d 2 r n p + p d n r ) , (38)
where C 1 C_1 C 1 is an absolute constant determined only by C 2 C_2 C 2 and c 0 c_0 c 0 . This bound also holds when τ = 0 \tau=0 τ = 0 . We estimate the two terms with the actual radius r = max { 6 , r 0 } r=\max\{6,r_0\} r = max { 6 , r 0 } . First, since r ≥ r 0 r\ge r_0 r ≥ r 0 ,
1 n d n p d 2 r ≤ n p n − 1 / 4 d 9 / 4 ≤ C − 9 / 4 . (39) \frac{1}{nd}\frac{np}{d^2\sqrt{r}}\le\frac{npn^{-1/4}}{d^{9/4}}\le C^{-9/4}. \tag*{(39)} n d 1 d 2 r n p ≤ d 9/4 n p n − 1/4 ≤ C − 9/4 . (39)
The last inequality follows since d 9 / 4 > ( C n − 1 / 9 p 4 / 9 ) 9 / 4 d^{9/4}>(Cn^{-1/9}p^{4/9})^{9/4} d 9/4 > ( C n − 1/9 p 4/9 ) 9/4 . For the second term, by the definition of r r r ,
p n d n r d = max { p n − 1 / 4 d 9 / 4 , 6 p n 1 / 2 d 3 / 2 } ≤ max { C − 9 / 4 , 6 C − 3 / 2 ( p / n ) 1 / 3 } ≤ 6 C − 3 / 2 . (40) \frac{p}{nd}\sqrt{\frac{nr}{d}}
=\max\left\{\frac{pn^{-1/4}}{d^{9/4}},\frac{\sqrt{6}p}{n^{1/2}d^{3/2}}\right\}
\le\max\left\{C^{-9/4},\sqrt{6}C^{-3/2}(p/n)^{1/3}\right\}
\le\sqrt{6}C^{-3/2}. \tag*{(40)} n d p d n r = max { d 9/4 p n − 1/4 , n 1/2 d 3/2 6 p } ≤ max { C − 9/4 , 6 C − 3/2 ( p / n ) 1/3 } ≤ 6 C − 3/2 . (40)
Here the second expression uses d 3 / 2 > C 3 / 2 n − 1 / 6 p 2 / 3 d^{3/2} > C^{3/2}n^{-1/6}p^{2/3} d 3/2 > C 3/2 n − 1/6 p 2/3 , and the final inequality uses p ≤ n p \le n p ≤ n and C ≥ 1 C \ge1 C ≥ 1 . Combining Equations (38) to (40) bounds the total loss by
C 1 ( C − 9 / 4 + 6 C − 3 / 2 ) n d . C_1\left(C^{-9/4}+\sqrt{6}C^{-3/2}\right)nd. C 1 ( C − 9/4 + 6 C − 3/2 ) n d .
Choose C C C large enough that the coefficient is at most 1 / 20 1/20 1/20 .
Closing the Induction
Fix C C C large enough that
C ≥ max { 30 , 2 13 / 9 C C E } , C 1 ( C − 9 / 4 + 6 C − 3 / 2 ) ≤ 1 / 20. C \ge\max\{30,2^{13/9}C_{\mathrm{CE}}\}, \qquad C_1\left(C^{-9/4}+\sqrt{6}C^{-3/2}\right) \le1/20. C ≥ max { 30 , 2 13/9 C CE } , C 1 ( C − 9/4 + 6 C − 3/2 ) ≤ 1/20.
This choice satisfies all preceding requirements. There is no circular dependence: C 1 C_1 C 1 depends only on the constants in the preliminary and technical lemmas, not on C C C .
Let R R R be the demand set at termination. By Lemmas 23 and 25 , at most n d 5 + n d 20 = n d 4 \frac{nd}{5}+\frac{nd}{20}=\frac{nd}{4} 5 n d + 20 n d = 4 n d edges have been deleted. Thus the residual graph satisfies
∣ E ( H ( R ) ) ∣ ≥ 3 4 n d . (41) \lvert E(H(R))\rvert\ge\frac{3}{4}nd. \tag*{(41)} ∣ E ( H ( R ))∣ ≥ 4 3 n d . (41)
It is a minimal distance preserver of ( G , R ) (G,R) ( G , R ) and ∣ R ∣ ≤ p / 2 \lvert R\rvert\le p/2 ∣ R ∣ ≤ p /2 . By Claim 22 ,
∣ E ( H ( R ) ) ∣ ≤ C n 8 / 9 ( p / 2 ) 4 / 9 = 2 − 4 / 9 C n 8 / 9 p 4 / 9 . (42) \lvert E(H(R))\rvert\le Cn^{8/9}(p/2)^{4/9}=2^{-4/9}Cn^{8/9}p^{4/9}. \tag*{(42)} ∣ E ( H ( R ))∣ ≤ C n 8/9 ( p /2 ) 4/9 = 2 − 4/9 C n 8/9 p 4/9 . (42)
Combining Equations (41) and (42) ,
n d ≤ 4 3 2 − 4 / 9 C n 8 / 9 p 4 / 9 < C n 8 / 9 p 4 / 9 , nd \le\frac{4}{3}2^{-4/9}Cn^{8/9}p^{4/9}<Cn^{8/9}p^{4/9}, n d ≤ 3 4 2 − 4/9 C n 8/9 p 4/9 < C n 8/9 p 4/9 ,
contradicting Equation (33) . The induction proves Equation (26) , and therefore proves Theorem 1 .
Pairwise Additive +2 Spanners
We apply the framework for minimal distance preservers to additive approximation. We keep the notation of Sections 5 and 6: R ⊆ P R \subseteq P R ⊆ P is the current demand set, H ( R ) H(R) H ( R ) is a minimal distance preserver of ( G , R ) (G,R) ( G , R ) , Q ⊆ R Q \subseteq R Q ⊆ R is a selected batch, and S S S is a set of vertices that covers or hits Q Q Q . We use J J J for the final additive spanner and J ( Q ) J(Q) J ( Q ) for the subgraph saved for a selected batch.
Definition 26 (Pairwise Additive + k +k + k Spanner). Given an integer k ≥ 0 k \ge0 k ≥ 0 , an n n n -vertex undirected unweighted graph G = ( V , E ) G=(V,E) G = ( V , E ) , and a demand set P ⊆ V × V P \subseteq V \times V P ⊆ V × V , a subgraph J ⊆ G J \subseteq G J ⊆ G is a pairwise additive + k +k + k spanner of ( G , P ) (G,P) ( G , P ) if
dist G ( s , t ) ≤ dist J ( s , t ) ≤ dist G ( s , t ) + k ( ( s , t ) ∈ P ) . \operatorname{dist}_{G}(s,t) \le\operatorname{dist}_{J}(s,t) \le\operatorname{dist}_{G}(s,t)+k \qquad((s,t)\in P). dist G ( s , t ) ≤ dist J ( s , t ) ≤ dist G ( s , t ) + k (( s , t ) ∈ P ) .
Theorem 27. Let G G G be any n n n -vertex undirected unweighted graph and let P P P be any set of p p p demand pairs. Then ( G , P ) (G,P) ( G , P ) admits a pairwise additive + 2 +2 + 2 spanner with O ( n + n 9 / 10 p 2 / 5 ) O(n+n^{9/10}p^{2/5}) O ( n + n 9/10 p 2/5 ) edges.
Proof strategy and comparison with the exact bound. Both Theorems 1 and 27 use minimal distance preservers and the extraction lemmas of § 5 . In each case, the goal is to handle a batch of Ω ( d 2 r ) \Omega(d^2\sqrt{r}) Ω ( d 2 r ) demands using vertices of diameter O ( r ) O(r) O ( r ) . The difference is the witness set. For Theorem 1 , a covering vertex lies on a shortest path, and Lemma 10 gives ∣ S ∣ = O ( ∣ Q ∣ / d ) |S| = O(|Q|/d) ∣ S ∣ = O ( ∣ Q ∣/ d ) . For the additive bound, a hitting vertex is adjacent to a shortest path, and Lemma 11 gives the smaller set ∣ S ∣ = O ( ∣ Q ∣ / d 2 ) |S| = O(|Q|/d^2) ∣ S ∣ = O ( ∣ Q ∣/ d 2 ) . Routing through a hitting vertex costs at most two extra edges. After splitting each demand at its chosen vertex of S S S , the respective bounds are
∣ E ( H ( Q ) ) ∣ = O ( n + ∣ Q ∣ n r d ) |E(H(Q))| = O\left(n + |Q|\sqrt{\frac{nr}{d}}\right) ∣ E ( H ( Q )) ∣ = O ( n + ∣ Q ∣ d n r )
for a covering set,
∣ E ( J ( Q ) ) ∣ = O ( n + ∣ Q ∣ n r d ) |E(J(Q))| = O\left(n + \frac{|Q|\sqrt{nr}}{d}\right) ∣ E ( J ( Q )) ∣ = O ( n + d ∣ Q ∣ n r )
for a hitting set.
Thus allowing additive error two saves a factor d \sqrt{d} d in the nonlinear batch cost.
There is also a difference in how these bounds are used. § 6 bounds every minimal distance preserver by an edge-count contradiction. Its exact batch preserver H ( Q ) H(Q) H ( Q ) bounds the number of edges lost after deleting Q Q Q , because minimality forces Equation (30) . A + 2 +2 + 2 spanner for Q Q Q does not give that union identity. Instead, we construct J J J explicitly: save each J ( Q ) J(Q) J ( Q ) in J J J , remove Q Q Q , and keep H ( R ) H(R) H ( R ) a minimal distance preserver for the remaining demands. The saved routes are compared with dist G \operatorname{dist}_G dist G , so taking their union does not accumulate additive error.
This explains the different treatment of short demands. The proof of Theorem 1 deletes demands of small private length. Here we first purchase shortest paths for demands of small original distance, at cost O ( p r ) O(pr) O ( p r ) . The remaining minimal distance preserver need not satisfy the private-edge hypotheses of Lemma 11 . Corollary 29 records the short extension of its proof that uses assigned essential demands and long full distances. It yields hitting sets in exactly the sense of Definition 9 , without requiring a second proof of the extraction argument.
The batch sizes remain Ω ( d 2 r ) \Omega(d^2\sqrt{r}) Ω ( d 2 r ) , so summing the additive batch costs gives
O ( n p d 2 r + p n r d ) . O\left(\frac{np}{d^2\sqrt{r}}+\frac{p\sqrt{nr}}{d}\right). O ( d 2 r n p + d p n r ) .
Balancing these terms gives r ≈ n / d r \approx\sqrt{n}/d r ≈ n / d , compared with r ≈ n d − 3 / 2 r \approx\sqrt{n}d^{-3/2} r ≈ n d − 3/2 for Theorem 1 . Including the final O ( n d ) O(nd) O ( n d ) minimal distance preserver gives d ≈ n − 1 / 10 p 2 / 5 d \approx n^{-1/10}p^{2/5} d ≈ n − 1/10 p 2/5 . We check the radius bounds, short-path cost, and endpoint ranges below.
Hitting Sets and Additive +2 Error
Let H H H be a minimal distance preserver, let S ⊆ V H S \subseteq V_H S ⊆ V H have finite diameter D D D , and let Q ∗ ⊆ S × V H Q^* \subseteq S \times V_H Q ∗ ⊆ S × V H be auxiliary demands. The same estimates used in Lemma 21 , namely Lemma 4 , give a minimal distance preserver H ( Q ∗ ) ⊆ H H(Q^*) \subseteq H H ( Q ∗ ) ⊆ H of ( H , Q ∗ ) (H,Q^*) ( H , Q ∗ ) with
∣ E ( H ( Q ∗ ) ) ∣ = O ( n + n ∣ Q ∗ ∣ ∣ S ∣ D ) . (43) |E(H(Q^*))| = O\left(n+\sqrt{n|Q^*||S|D}\right). \tag*{(43)} ∣ E ( H ( Q ∗ )) ∣ = O ( n + n ∣ Q ∗ ∣∣ S ∣ D ) . (43)
For a singleton S S S , choose a BFS tree rooted at its vertex and then a minimal subgraph preserving the auxiliary demands. This gives O ( n ) O(n) O ( n ) edges also when D = 0 D=0 D = 0 .
Lemma 28 (A hitting set gives an additive spanner). Let H H H be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) on at most n n n vertices. Let ∅ ≠ Q ⊆ R \varnothing\ne Q \subseteq R ∅ = Q ⊆ R , and suppose that a nonempty set S ⊆ V H S \subseteq V_H S ⊆ V H hits Q Q Q in $H, with
D = diam H ( S ) < ∞ D = \operatorname{diam}_{H}(S) < \infty D = diam H ( S ) < ∞ . Then there is a pairwise additive + 2 +2 + 2 spanner J ( Q ) ⊆ H J(Q) \subseteq H J ( Q ) ⊆ H of ( G , Q ) (G,Q) ( G , Q ) satisfying
∣ E ( J ( Q ) ) ∣ = O ( n + n ∣ Q ∣ ∣ S ∣ D ) . (44) |E(J(Q))| = O\left(n + \sqrt{n|Q||S|D}\right). \tag*{(44)} ∣ E ( J ( Q )) ∣ = O ( n + n ∣ Q ∣∣ S ∣ D ) . (44)
Proof. For each q = ( s , t ) ∈ Q q=(s,t)\in Q q = ( s , t ) ∈ Q , choose a hitting tuple ( u q , x q , e q ) (u_q,x_q,e_q) ( u q , x q , e q ) with u q ∈ S u_q\in S u q ∈ S . By Definition 9 , the edge e q e_q e q is essential to q q q , x q x_q x q is an endpoint of e q e_q e q , and u q x q ∈ E H u_qx_q\in E_H u q x q ∈ E H . Thus x q x_q x q lies on every shortest path for q q q in H H H , and
dist H ( s , x q ) + dist H ( x q , t ) = dist H ( s , t ) = dist G ( s , t ) . \operatorname{dist}_{H}(s,x_q)+\operatorname{dist}_{H}(x_q,t)=\operatorname{dist}_{H}(s,t)=\operatorname{dist}_{G}(s,t). dist H ( s , x q ) + dist H ( x q , t ) = dist H ( s , t ) = dist G ( s , t ) .
It follows that
dist H ( s , u q ) + dist H ( u q , t ) ≤ dist H ( s , x q ) + 1 + 1 + dist H ( x q , t ) = dist G ( s , t ) + 2. (45) \operatorname{dist}_{H}(s,u_q)+\operatorname{dist}_{H}(u_q,t)\leq\operatorname{dist}_{H}(s,x_q)+1+1+\operatorname{dist}_{H}(x_q,t)
=\operatorname{dist}_{G}(s,t)+2. \tag*{(45)} dist H ( s , u q ) + dist H ( u q , t ) ≤ dist H ( s , x q ) + 1 + 1 + dist H ( x q , t ) = dist G ( s , t ) + 2. (45)
Form the split demand set, as in Lemma 21 ,
Q ∗ = ⋃ q = ( s , t ) ∈ Q { ( u q , s ) , ( u q , t ) } ⊆ S × V H , Q^*=\bigcup_{q=(s,t)\in Q}\{(u_q,s),(u_q,t)\}\subseteq S\times V_H, Q ∗ = q = ( s , t ) ∈ Q ⋃ {( u q , s ) , ( u q , t )} ⊆ S × V H ,
omitting repeated and trivial pairs. Hence ∣ Q ∗ ∣ ≤ 2 ∣ Q ∣ |Q^*|\leq2|Q| ∣ Q ∗ ∣ ≤ 2∣ Q ∣ . Choose the minimal distance preserver H ( Q ∗ ) H(Q^*) H ( Q ∗ ) in Equation (43) and set J ( Q ) = H ( Q ∗ ) J(Q)=H(Q^*) J ( Q ) = H ( Q ∗ ) . Concatenating its two preserved routes through u q u_q u q and using Equation (45) gives
dist J ( Q ) ( s , t ) ≤ dist G ( s , t ) + 2. \operatorname{dist}_{J(Q)}(s,t)\leq\operatorname{dist}_{G}(s,t)+2. dist J ( Q ) ( s , t ) ≤ dist G ( s , t ) + 2.
The lower bound follows from J ( Q ) ⊆ G J(Q)\subseteq G J ( Q ) ⊆ G . The edge bound follows from ∣ Q ∗ ∣ ≤ 2 ∣ Q ∣ |Q^*|\leq2|Q| ∣ Q ∗ ∣ ≤ 2∣ Q ∣ . When S S S is a singleton, its BFS-tree construction handles all demand endpoints in the component of its root.
Hitting Sets for Long Demands
We use Lemma 11 through the following assigned-demand form. We retain the notation D H R ( e ) D_H^R(e) D H R ( e ) for the full essential-demand set. A chosen demand-label l ( e ) ∈ D H R ( e ) l(e)\in D_H^R(e) l ( e ) ∈ D H R ( e ) need not be the unique essential demand, so the notation D ( e ) = q D(e)=q D ( e ) = q for a private edge is not used for these labels.
Corollary 29. Let H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) be a minimal distance preserver of ( G , R ) (G,R) ( G , R ) , retaining all n n n vertices, and put d H = ∣ E H ∣ / n d_H=|E_H|/n d H = ∣ E H ∣/ n . Suppose that dist H ( q ) ≥ r \operatorname{dist}_H(q)\geq r dist H ( q ) ≥ r for every q ∈ R q\in R q ∈ R , where 6 ≤ r ≤ d H 2 6\leq r\leq d_H^2 6 ≤ r ≤ d H 2 . There are nonempty sets Q ⊆ R Q\subseteq R Q ⊆ R and S ⊆ V H S\subseteq V_H S ⊆ V H such that S S S hits Q Q Q in H H H and
∣ Q ∣ = Ω ( d H 2 r ) , ∣ S ∣ = O ( ∣ Q ∣ / d H 2 ) , diam H ( S ) ≤ 8 r . (46) |Q|=\Omega(d_H^2\sqrt{r}),\qquad|S|=O(|Q|/d_H^2),\qquad\operatorname{diam}_H(S)\leq8r. \tag*{(46)} ∣ Q ∣ = Ω ( d H 2 r ) , ∣ S ∣ = O ( ∣ Q ∣/ d H 2 ) , diam H ( S ) ≤ 8 r . (46)
Proof. Assign each edge a demand-label l ( e ) ∈ D H R ( e ) l(e)\in D_H^R(e) l ( e ) ∈ D H R ( e ) , which exists by minimality. Repeatedly remove vertices of current degree less than d H / 40 d_H/40 d H /40 . Fewer than n d H / 40 nd_H/40 n d H /40 edges are removed, so the remaining auxiliary core H C = ( V C , E C ) H_C=(V_C,E_C) H C = ( V C , E C ) satisfies
∣ E C ∣ ≥ 39 40 n d H , deg H C ( x ) ≥ d H 40 ( x ∈ V C ) . |E_C|\geq\frac{39}{40}nd_H,\qquad\deg_{H_C}(x)\geq\frac{d_H}{40}\quad(x\in V_C). ∣ E C ∣ ≥ 40 39 n d H , deg H C ( x ) ≥ 40 d H ( x ∈ V C ) .
This core need not consist of private edges. It supplies only the selected edges and neighbors; all distances, balls, and essentiality are measured in the unchanged graph H H H .
Apply the proof of Lemma 11 with density parameter d = d H d=d_H d = d H and length parameter l = r l=r l = r . The ball-growth proof in Lemma 14 uses private length at least l l l only to imply full demand distance at least l. That condition holds here directly: when 2 ( j − 1 ) < r 2(j-1)<r 2 ( j − 1 ) < r , the endpoints of a labelled demand cannot both lie in a radius-( j − 1 ) (j-1) ( j − 1 ) ball, giving the same BFS-tree covering argument.
The proofs of Lemmas 15 to 17 use only essentiality to the fixed label. All edges labelled q q q lie on a fixed shortest path for q q q , giving the same bound of six hitting tuples per vertex–demand incidence. Also, preserving q q q exactly forces every edge assigned to q q q . Thus the charging, localization, clustering, and partial-cover arguments apply to E C E_C E C with these labels. The radius condition is 6 ≤ r ≤ min { d H 2 , l } 6 \le r \le\min\{d_H^2,l\} 6 ≤ r ≤ min { d H 2 , l } with l = r l=r l = r . The proof gives Equation (46) , and its witness tuples show that S S S hits Q Q Q according to Definition 9.
Corollary 30 (Spanner for an extracted demand set). Under the hypotheses of Corollary 29 , its demand set Q Q Q has a pairwise additive + 2 +2 + 2 spanner J ( Q ) ⊆ H J(Q) \subseteq H J ( Q ) ⊆ H of ( G , Q ) (G,Q) ( G , Q ) with
∣ E ( J ( Q ) ) ∣ = O ( n + ∣ Q ∣ n r d H ) . (47) |E(J(Q))| = O\left(n+\frac{|Q|\sqrt{nr}}{d_H}\right). \tag*{(47)} ∣ E ( J ( Q )) ∣ = O ( n + d H ∣ Q ∣ n r ) . (47)
Proof. Apply Lemma 28 to the hitting set S S S from Equation (46) . Its edge bound is
O ( n + n ∣ Q ∣ ( ∣ Q ∣ / d H 2 ) r ) = O ( n + ∣ Q ∣ n r d H ) . O\left(n+\sqrt{n|Q|(|Q|/d_H^2)r}\right)=O\left(n+\frac{|Q|\sqrt{nr}}{d_H}\right). O ( n + n ∣ Q ∣ ( ∣ Q ∣/ d H 2 ) r ) = O ( n + d H ∣ Q ∣ n r ) .
Demand Removal and the Final Spanner
As in Section 6, we keep the parameters n , p , d , r n,p,d,r n , p , d , r fixed while changing R R R and its minimal distance preserver H ( R ) H(R) H ( R ) . Here d d d is the density threshold at which the construction stops. When H ( R ) H(R) H ( R ) has more than n d nd n d edges, its current density d R = ∣ E ( H ( R ) ) ∣ / n d_R=|E(H(R))|/n d R = ∣ E ( H ( R )) ∣/ n is greater than d d d ; we apply Corollary 29 with d H = d R d_H=d_R d H = d R .
Lemma 31 (A parameterized demand-removal construction). For every d ≥ 6 d \ge\sqrt{6} d ≥ 6 and 6 ≤ r ≤ d 2 6 \le r \le d^2 6 ≤ r ≤ d 2 , there is a pairwise additive + 2 +2 + 2 spanner of ( G , P ) (G,P) ( G , P ) with edge size
O ( p r + n d + n p d 2 r + p n r d ) . (48) O\left(pr+nd+\frac{np}{d^2\sqrt{r}}+\frac{p\sqrt{nr}}{d}\right). \tag*{(48)} O ( p r + n d + d 2 r n p + d p n r ) . (48)
Proof. We construct a spanning subgraph J ⊆ G J \subseteq G J ⊆ G as follows.
Preserve short demands exactly. Let P s h o r t = { q ∈ P : dist G ( q ) < r } P_{\mathrm{short}}=\{q\in P:\operatorname{dist}_G(q)<r\} P short = { q ∈ P : dist G ( q ) < r } . Add one G G G -shortest path for each demand in P s h o r t P_{\mathrm{short}} P short to J J J , at a cost of at most p r pr p r edges. Set R = P ∖ P s h o r t R=P\setminus P_{\mathrm{short}} R = P ∖ P short and choose a minimal distance preserver H ( R ) ⊆ G H(R)\subseteq G H ( R ) ⊆ G of ( G , R ) (G,R) ( G , R ) . The original set P P P and its size p p p remain fixed.
Save a spanner for a hit batch. While ∣ E ( H ( R ) ) ∣ > n d |E(H(R))|>nd ∣ E ( H ( R )) ∣ > n d , set d R = ∣ E ( H ( R ) ) ∣ / n > d d_R=|E(H(R))|/n>d d R = ∣ E ( H ( R )) ∣/ n > d . Every active demand has distance at least r r r , and r ≤ d 2 < d R 2 r\le d^2<d_R^2 r ≤ d 2 < d R 2 . Apply Corollary 29 and save the resulting subgraph J ( Q ) J(Q) J ( Q ) from Corollary 30 by adding it to J J J . Set R ′ = R ∖ Q R'=R\setminus Q R ′ = R ∖ Q , and choose a minimal distance preserver H ( R ′ ) ⊆ H ( R ) H(R')\subseteq H(R) H ( R ′ ) ⊆ H ( R ) of ( H ( R ) , R ′ ) (H(R),R') ( H ( R ) , R ′ ) . Continue with R ← R ′ R\leftarrow R' R ← R ′ . As in Section 6, such an update is obtained by sequential edge deletions that preserve the required distances; essential-demand sets and demand-labels are recomputed in each new instance.
Include the final minimal distance preserver. When ∣ E ( H ( R ) ) ∣ ≤ n d |E(H(R))|\le nd ∣ E ( H ( R )) ∣ ≤ n d , add all its edges to J J J and stop.
Correctness and termination. For each demand q ∈ R q \in R q ∈ R , it always satisfies that
dist H ( R ) ( q ) = dist G ( q ) ( q ∈ R ) . (49) \operatorname{dist}_{H(R)}(q) = \operatorname{dist}_{G}(q) \qquad(q \in R). \tag*{(49)} dist H ( R ) ( q ) = dist G ( q ) ( q ∈ R ) . (49)
It holds initially because H ( R ) H(R) H ( R ) is a distance preserver of ( G , R ) (G,R) ( G , R ) . The update preserves the old H ( R ) H(R) H ( R ) -distances exactly, so the equality continues to hold for R ′ R' R ′ . Its minimality also makes H ( R ′ ) H(R') H ( R ′ ) a minimal distance preserver of ( G , R ′ ) (G,R') ( G , R ′ ) . Thus every invocation of Corollary 29 is in a valid current instance. Each batch Q Q Q is nonempty, so the loop terminates after at most p p p iterations.
The demands removed in Step 1 have exact routes in J J J . Each batch removed in Step 2 has a saved route of length at most dist G ( q ) + 2 \operatorname{dist}_{G}(q) + 2 dist G ( q ) + 2 , by Lemma 28 and Eq. (49) . Demands remaining in Step 3 have exact routes in the final minimal distance preserver. None of the saved subgraphs is deleted from J J J . Therefore J J J is a pairwise additive + 2 +2 + 2 spanner of ( G , P ) (G,P) ( G , P ) . This argument does not replace parts of a demand path by several approximate routes: each processed demand has a complete certificate relative to its original distance in G G G .
Edge count. Let Q 1 , … , Q τ Q_1,\ldots,Q_\tau Q 1 , … , Q τ be the batches removed in Step 2, and let d i d_i d i be the corresponding value of d R d_R d R . The batches are disjoint subsets of the original P P P , and Corollary 29 gives
∑ i = 1 τ ∣ Q i ∣ ≤ p , ∣ Q i ∣ = Ω ( d i 2 r ) = Ω ( d 2 r ) , τ = O ( p d 2 r ) . \sum_{i=1}^{\tau} |Q_i| \le p,\qquad|Q_i| = \Omega(d_i^2\sqrt{r}) = \Omega(d^2\sqrt{r}),\qquad\tau= O\left(\frac{p}{d^2\sqrt{r}}\right). i = 1 ∑ τ ∣ Q i ∣ ≤ p , ∣ Q i ∣ = Ω ( d i 2 r ) = Ω ( d 2 r ) , τ = O ( d 2 r p ) .
By Equation (47) , the total number of saved batch edges is at most
∑ i = 1 τ O ( n + ∣ Q i ∣ n r d i ) ≤ O ( n τ + n r d ∑ i = 1 τ ∣ Q i ∣ ) = O ( n p d 2 r + p n r d ) . \begin{aligned}
\sum_{i=1}^{\tau} O\left(n+\frac{|Q_i|\sqrt{nr}}{d_i}\right)
\le O\left(n\tau+\frac{\sqrt{nr}}{d}\sum_{i=1}^{\tau}|Q_i|\right) \\
&= O\left(\frac{np}{d^2\sqrt{r}}+\frac{p\sqrt{nr}}{d}\right).
\end{aligned} i = 1 ∑ τ O ( n + d i ∣ Q i ∣ n r ) ≤ O ( n τ + d n r i = 1 ∑ τ ∣ Q i ∣ ) = O ( d 2 r n p + d p n r ) .
Adding the at most p r pr p r initial path edges and the at most n d nd n d final edges proves Equation (48) . The same bound holds if no batch is extracted.
Complete the Proof of Theorem 27 For large demand sets, we use the following classical all-pairs additive spanner bound.
Theorem 32 (Elkin–Peleg [21 Theorem 3.22(1)] ). Every n n n -vertex undirected unweighted graph has an all-pairs additive + 2 +2 + 2 spanner with O ( n 3 / 2 ) O(n^{3/2}) O ( n 3/2 ) edges.
Proof of Theorem 27. Put T = n 9 / 10 p 2 / 5 T=n^{9/10}p^{2/5} T = n 9/10 p 2/5 . If p < n 2 / 3 p<n^{2/3} p < n 2/3 , Lemma 2 gives a minimal distance preserver of size O ( n + n p ) O(n+\sqrt{n}\,p) O ( n + n p ) , and
n p T = n − 2 / 5 p 3 / 5 ≤ 1. \frac{\sqrt{n}\,p}{T}=n^{-2/5}p^{3/5}\le1. T n p = n − 2/5 p 3/5 ≤ 1.
If p > n 3 / 2 p>n^{3/2} p > n 3/2 , by Theorem 32, we have n 3 / 2 ≤ T n^{3/2}\le T n 3/2 ≤ T . It remains to consider n 2 / 3 ≤ p ≤ n 3 / 2 n^{2/3}\le p\le n^{3/2} n 2/3 ≤ p ≤ n 3/2 . Fix the parameters
d = 3 n − 1 / 10 p 2 / 5 , r = max { 6 , n / d } . (50) d=3n^{-1/10}p^{2/5},\qquad r=\max\{6,\sqrt{n}/d\}. \tag*{(50)} d = 3 n − 1/10 p 2/5 , r = max { 6 , n / d } . (50)
Here d ≥ 3 n 1 / 6 d\ge3n^{1/6} d ≥ 3 n 1/6 , so d 2 ≥ 6 d^2\ge6 d 2 ≥ 6 and d 3 ≥ 27 n d^3\ge27\sqrt{n} d 3 ≥ 27 n . Consequently 6 ≤ r ≤ d 2 6\le r\le d^2 6 ≤ r ≤ d 2 , allowing Lemma 31. The maximum with six ensures the technical radius condition even when the balanced value n / d \sqrt{n}/d n / d is small.
We bound the four costs in Equation (48) using the actual radius in Equation (50) . First, n d = 3 T nd = 3T n d = 3 T . Since r ≥ n / d r \ge\sqrt{n}/d r ≥ n / d ,
n p d 2 r ≤ p n 3 / 4 d 3 / 2 = 3 − 3 / 2 T . (51) \frac{np}{d^2\sqrt{r}} \le\frac{pn^{3/4}}{d^{3/2}} = 3^{-3/2}T. \tag*{(51)} d 2 r n p ≤ d 3/2 p n 3/4 = 3 − 3/2 T . (51)
Also r ≤ 6 + n 1 / 4 d − 1 / 2 \sqrt{r} \le\sqrt{6}+n^{1/4}d^{-1/2} r ≤ 6 + n 1/4 d − 1/2 , hence
p n r d ≤ 6 p n d + p n 3 / 4 d 3 / 2 . \frac{p\sqrt{nr}}{d} \le\frac{\sqrt{6}p\sqrt{n}}{d}+\frac{pn^{3/4}}{d^{3/2}}. d p n r ≤ d 6 p n + d 3/2 p n 3/4 .
The second term is bounded in Equation (51) . For the first, p ≤ n 3 / 2 p \le n^{3/2} p ≤ n 3/2 gives
p n d = 1 3 n 3 / 5 p 3 / 5 ≤ T / 3. \frac{p\sqrt{n}}{d}=\frac{1}{3}n^{3/5}p^{3/5}\le T/3. d p n = 3 1 n 3/5 p 3/5 ≤ T /3.
Finally,
p r ≤ 6 p + p n d = O ( T ) , pr \le6p+\frac{p\sqrt{n}}{d}=O(T), p r ≤ 6 p + d p n = O ( T ) ,
since p / T = n − 9 / 10 p 3 / 5 ≤ 1 p/T=n^{-9/10}p^{3/5}\le1 p / T = n − 9/10 p 3/5 ≤ 1 in this range. Substitution into Equation (48) proves the claimed bound for all demand counts.
More Results on Additive Spanner Bounds
We derive the remaining bounds in Table 1 from Theorem 1 and classical preserver bounds using the path-sampling and clustering framework of [26 ] , with the constant-fraction completion argument of [12 ] . We give the reductions explicitly. Throughout, G = ( V , E ) G=(V,E) G = ( V , E ) is an undirected unweighted graph with n n n vertices, P P P is a demand set of size p p p , and J ⊆ G J\subseteq G J ⊆ G denotes an additive spanner, as in Definition 26 . All subgraphs retain V V V , and all distance guarantees are relative to G G G . We may discard trivial and unreachable demands and assume n ≥ 2 n\ge2 n ≥ 2 ; empty demand or source sets require no edges.
Definition 33 (Source-sensitive and sourcewise spanners). Let S ⊆ V S\subseteq V S ⊆ V have size σ \sigma σ and let β ≥ 0 \beta\ge0 β ≥ 0 be an integer. For P ⊆ S × V P\subseteq S\times V P ⊆ S × V , a source-sensitive additive + β +\beta + β spanner is a subgraph J ⊆ G J\subseteq G J ⊆ G such that
dist J ( s , t ) ≤ dist G ( s , t ) + β ( ( s , t ) ∈ P ) . \operatorname{dist}_{J}(s,t)\le\operatorname{dist}_{G}(s,t)+\beta\qquad((s,t)\in P). dist J ( s , t ) ≤ dist G ( s , t ) + β (( s , t ) ∈ P ) . A complete sourcewise additive + β +\beta + β spanner satisfies this inequality for every reachable pair in S × V S\times V S × V . For unordered demands, P ⊆ S × V P\subseteq S\times V P ⊆ S × V means that each demand has been oriented with its first endpoint in S S S .
We use the following exact-preserver bounds:
O ( n + n 8 / 9 q 4 / 9 ) for q ≤ n , (52) O(n+n^{8/9}q^{4/9}) \qquad\text{for } q\le n, \tag*{(52)} O ( n + n 8/9 q 4/9 ) for q ≤ n , (52)
O ( n + n q ) for all q . (53) O(n+\sqrt{n}\,q) \qquad\text{for all } q. \tag*{(53)} O ( n + n q ) for all q . (53)
Here (53) is Lemma 2, and (52) follows from Theorem 1 , using (53) when q < n q<\sqrt{n} q < n . In particular, at most n \sqrt{n} n demands have an O ( n ) O(n) O ( n ) -edge exact preserver.
Two common reductions
Lemma 34 (Sampling reduction). Let p > 0 p>0 p > 0 , d ≥ 1 d\ge1 d ≥ 1 , and let β ≥ 0 \beta\ge0 β ≥ 0 be an integer. Each of the following constructions provides a subgraph J 0 ⊆ G J_0\subseteq G J 0 ⊆ G with O ( n d ) O(nd) O ( n d ) edges and a set R ⊆ V R\subseteq V R ⊆ V with ∣ R ∣ ≤ p / d 2 |R|\le p/d^2 ∣ R ∣ ≤ p / d 2 .
(i) If P ⊆ S × V P \subseteq S \times V P ⊆ S × V , adjoining any additive + β +\beta + β spanner for the reachable pairs in S × R S \times R S × R satisfies at least half of P P P with additive error β + 2 \beta+ 2 β + 2 .
(ii) For arbitrary P P P , adjoining any additive + β +\beta + β spanner for the reachable pairs in R × R R \times R R × R satisfies at least half of P P P with additive error β + 4 \beta+ 4 β + 4 .
The choices of J 0 J_0 J 0 and R R R may differ between the two constructions.
Proof. Put Δ = ⌈ 4 d ⌉ \Delta= \lceil4d \rceil Δ = ⌈ 4 d ⌉ and ℓ = ⌈ n Δ / p ⌉ \ell= \lceil n\Delta/p \rceil ℓ = ⌈ n Δ/ p ⌉ . Form B ⊆ G B \subseteq G B ⊆ G by retaining Δ \Delta Δ arbitrary incident edges at each vertex, or all its incident edges if fewer exist. Thus ∣ E ( B ) ∣ ≤ n Δ |E(B)| \le n\Delta ∣ E ( B ) ∣ ≤ n Δ . For each demand ( s , t ) ∈ P (s,t) \in P ( s , t ) ∈ P , choose an arbitrary shortest s s s –t t t path in G G G , denote it by π ( s , t ) \pi(s,t) π ( s , t ) , and traverse it from s s s to t t t . In (i), use the orientation with s ∈ S s \in S s ∈ S ; in (ii), either orientation may be chosen. These paths remain fixed throughout this construction. The argument uses only shortestness of each individual path, so the choices for different demands may be made independently. Throughout this proof, a missing edge means an edge absent from this fixed B B B .
For (i), purchase all missing edges of a path if there are fewer than ℓ \ell ℓ ; otherwise purchase its last ℓ − 1 \ell- 1 ℓ − 1 missing edges. For (ii), purchase all missing edges if there are fewer than 2 ℓ − 1 2\ell- 1 2 ℓ − 1 ; otherwise purchase its first and last ℓ − 1 \ell- 1 ℓ − 1 missing edges. Here the first and last missing edges are ordered along π ( s , t ) \pi(s,t) π ( s , t ) from s s s to t t t . All purchases are made relative to B B B , even if an edge has already been purchased for another demand. Let J 0 J_0 J 0 be B B B together with these purchases. In either case their total cost is at most n Δ + 2 p ( ℓ − 1 ) < 3 n Δ = O ( n d ) n\Delta+ 2p(\ell- 1) < 3n\Delta= O(nd) n Δ + 2 p ( ℓ − 1 ) < 3 n Δ = O ( n d ) .
For a path not bought entirely, in (i) consider the heads of its last ℓ \ell ℓ missing edges; in (ii) also consider the tails of its first ℓ \ell ℓ missing edges. Every endpoint of a missing edge has at least Δ \Delta Δ neighbors in B B B : a vertex of degree at most Δ \Delta Δ would have retained all its incident edges. For a demand q q q , let A q + A_q^+ A q + be the union of the B B B -neighbors of its chosen heads, and in (ii) let A q − A_q^- A q − be the analogous union for its chosen tails. Each list has ℓ \ell ℓ distinct vertices, since the chosen path is simple. Any vertex is adjacent to at most three vertices of a shortest path: the subpath between its first and last neighbors has length at most two, using the route through that vertex. Counting incidences between the list and its B B B -neighbors therefore gives
∣ A q + ∣ ≥ ℓ Δ / 3 , ∣ A q − ∣ ≥ ℓ Δ / 3 in (ii). |A_q^+| \ge\ell\Delta/3,\qquad|A_q^-| \ge\ell\Delta/3\quad\text{in (ii).} ∣ A q + ∣ ≥ ℓ Δ/3 , ∣ A q − ∣ ≥ ℓ Δ/3 in (ii).
The suffix from each chosen head to t t t , and in (ii) the prefix from s s s to each chosen tail, belongs to J 0 J_0 J 0 . In (ii) every chosen tail precedes every chosen head, even when the two lists of missing edges share their middle edge.
If every path was bought entirely, take R = ∅ R = \varnothing R = ∅ ; then J 0 J_0 J 0 already preserves every demand exactly. Otherwise one of these neighborhoods exists, and its size is at most n n n , so ℓ Δ ≤ 3 n \ell\Delta\le3n ℓ Δ ≤ 3 n . Sample m = ⌈ 12 n / ( ℓ Δ ) ⌉ m = \lceil12n/(\ell\Delta)\rceil m = ⌈ 12 n / ( ℓ Δ )⌉ vertices independently and uniformly with replacement, and let R R R be their set. Then
∣ R ∣ ≤ m ≤ 15 n ℓ Δ ≤ 15 p Δ 2 ≤ p d 2 . |R| \le m \le\frac{15n}{\ell\Delta} \le\frac{15p}{\Delta^2} \le\frac{p}{d^2}. ∣ R ∣ ≤ m ≤ ℓ Δ 15 n ≤ Δ 2 15 p ≤ d 2 p .
For each indicated neighborhood A A A , the probability that it contains no sampled vertex is
Pr ( R ∩ A = ∅ ) = ( 1 − ∣ A ∣ n ) m ≤ exp ( − m ∣ A ∣ n ) ≤ e − 4 . \Pr(R \cap A = \varnothing) = \left(1-\frac{|A|}{n}\right)^m \le\exp\left(-\frac{m|A|}{n}\right) \le e^{-4}. Pr ( R ∩ A = ∅ ) = ( 1 − n ∣ A ∣ ) m ≤ exp ( − n m ∣ A ∣ ) ≤ e − 4 .
In (i), a sampled neighbor z z z of a chosen head v v v gives, after adding the auxiliary spanner, a route of length at most
dist G ( s , z ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 2. \operatorname{dist}_G(s,z) + \beta+ 1 + \operatorname{dist}_G(v,t) \le\operatorname{dist}_G(s,t) + \beta+ 2. dist G ( s , z ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 2.
Here z v ∈ E ( B ) zv \in E(B) z v ∈ E ( B ) gives dist G ( s , z ) ≤ dist G ( s , v ) + 1 \operatorname{dist}_{G}(s,z) \le\operatorname{dist}_{G}(s,v) + 1 dist G ( s , z ) ≤ dist G ( s , v ) + 1 , and the chosen path gives dist G ( s , v ) + dist G ( v , t ) = dist G ( s , t ) \operatorname{dist}_{G}(s,v) + \operatorname{dist}_{G}(v,t) = \operatorname{dist}_{G}(s,t) dist G ( s , v ) + dist G ( v , t ) = dist G ( s , t ) . In (ii), sampled neighbors a , b a,b a , b of a chosen tail u u u and head v v v give a route of length at most
dist G ( s , u ) + 1 + dist G ( a , b ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 4. \operatorname{dist}_{G}(s,u) + 1 + \operatorname{dist}_{G}(a,b) + \beta+ 1 + \operatorname{dist}_{G}(v,t) \le\operatorname{dist}_{G}(s,t) + \beta+ 4. dist G ( s , u ) + 1 + dist G ( a , b ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 4.
The bound on the route length uses the auxiliary distance guarantee. The displayed inequality follows from dist G ( a , b ) ≤ 1 + dist G ( u , v ) + 1 \operatorname{dist}_{G}(a,b) \le1 + \operatorname{dist}_{G}(u,v) + 1 dist G ( a , b ) ≤ 1 + dist G ( u , v ) + 1 and the fact that u u u precedes v v v on a shortest s s s –t t t path. In (i) it suffices that R R R meets A q + A_q^+ A q + ; in (ii) it suffices that R R R meets both A q − A_q^- A q − and A q + A_q^+ A q + . A union bound shows that each demand not bought entirely has these witnesses with probability at least 1 − 2 e − 4 > 1 / 2 1 - 2e^{-4} > 1/2 1 − 2 e − 4 > 1/2 . Demands bought entirely always succeed. Let X X X count demands with such certificates. By linearity of expectation,
E [ X ] ≥ ( 1 − 2 e − 4 ) p > p / 2. \mathbb{E}[X] \ge(1 - 2e^{-4})p > p/2. E [ X ] ≥ ( 1 − 2 e − 4 ) p > p /2.
Hence some sampling outcome certifies at least half the demands. The certificates use only the stated auxiliary distance guarantees, so they work for any auxiliary spanner satisfying those guarantees. The edge and sample-size bounds hold for every outcome, proving the lemma. □
Lemma 35 (Completion from a constant fraction). Fix an additive error β \beta β and a source set S S S , if applicable. Suppose that, whenever p > n p > \sqrt{n} p > n , at least half the demands can be satisfied with O ( f ( n , σ , p ) ) O(f(n,\sigma,p)) O ( f ( n , σ , p )) edges, where f ( n , σ , p ) = A ( n , σ ) p η f(n,\sigma,p) = A(n,\sigma)p^\eta f ( n , σ , p ) = A ( n , σ ) p η , with fixed η > 0 \eta> 0 η > 0 , and f ( n , σ , p ) ≥ n f(n,\sigma,p) \ge n f ( n , σ , p ) ≥ n for these demand counts. If the construction’s hypotheses persist on demand subsets, then all demands have an additive + β +\beta + β spanner with O ( n + f ( n , σ , p ) ) O(n + f(n,\sigma,p)) O ( n + f ( n , σ , p )) edges.
Proof. If p ≤ n p \le\sqrt{n} p ≤ n , (53) gives an exact preserver with O ( n ) O(n) O ( n ) edges. Otherwise repeat the constant-fraction construction on the unsatisfied demands in the original graph G G G , keeping S S S fixed. After i i i rounds, at most p / 2 i p/2^i p / 2 i demands remain. Since η > 0 \eta> 0 η > 0 , the successive costs sum geometrically:
∑ i ≥ 0 O ( A ( n , σ ) ( p / 2 i ) η ) = O ( f ( n , σ , p ) 1 − 2 − η ) = O ( f ( n , σ , p ) ) . \sum_{i \ge0} O\left(A(n,\sigma)(p/2^i)^\eta\right) = O\left(\frac{f(n,\sigma,p)}{1 - 2^{-\eta}}\right) = O(f(n,\sigma,p)). i ≥ 0 ∑ O ( A ( n , σ ) ( p / 2 i ) η ) = O ( 1 − 2 − η f ( n , σ , p ) ) = O ( f ( n , σ , p )) . Finish with (53) when at most n \sqrt{n} n demands remain. Every round supplies complete routes for its satisfied demands relative to their distances in G G G . Their union retains all these routes, so the additive error remains β \beta β throughout the completion. □
Pairwise and source-sensitive bounds
Theorem 36. For every set P P P of p ≤ n 7 / 6 p \le n^{7/6} p ≤ n 7/6 demand pairs, ( G , P ) (G,P) ( G , P ) admits a pairwise additive + 4 +4 + 4 spanner with O ( n + n 24 / 25 p 8 / 25 ) O(n + n^{24/25}p^{8/25}) O ( n + n 24/25 p 8/25 ) edges.
Proof. The case p ≤ n p \le\sqrt{n} p ≤ n follows from (53) . Otherwise set d = n − 1 / 25 p 8 / 25 > 1 d = n^{-1/25}p^{8/25} > 1 d = n − 1/25 p 8/25 > 1 and apply Lemma 34(ii) with an exact auxiliary preserver. Its demand count is
q ≤ ∣ R ∣ 2 ≤ p 2 / d 4 = n 4 / 25 p 18 / 25 ≤ n . q \le|R|^2 \le p^2/d^4 = n^{4/25}p^{18/25} \le n. q ≤ ∣ R ∣ 2 ≤ p 2 / d 4 = n 4/25 p 18/25 ≤ n . Hence (52) applies and costs O ( n + n 8 / 9 ( p 2 / d 4 ) 4 / 9 ) = O ( n d ) O(n + n^{8/9}(p^2/d^4)^{4/9}) = O(nd) O ( n + n 8/9 ( p 2 / d 4 ) 4/9 ) = O ( n d ) . The sampling step therefore satisfies half the demands at cost O ( n d ) = O ( n 24 / 25 p 8 / 25 ) O(nd) = O(n^{24/25}p^{8/25}) O ( n d ) = O ( n 24/25 p 8/25 ) . Here n d > n nd > n n d > n , and the range p ≤ n 7 / 6 p \le n^{7/6} p ≤ n 7/6 persists when demands are removed. Thus Lemma 35, with η = 8 / 25 \eta= 8/25 η = 8/25 , proves the claim. □
Theorem 37 (Source-sensitive bounds). Let P ⊆ S × V P \subseteq S \times V P ⊆ S × V and ∣ S ∣ = σ |S| = \sigma ∣ S ∣ = σ . For every fixed integer k ≥ 1 k \ge1 k ≥ 1 , if p σ k ≤ n 1 + 2 k / 3 p\sigma^k \le n^{1+2k/3} p σ k ≤ n 1 + 2 k /3 , then ( G , P ) (G,P) ( G , P ) admits an additive + 2 k +2k + 2 k spanner with
O k ( n + F k ( n , σ , p ) ) edges , F k ( n , σ , p ) = n ( 8 + 8 k ) / ( 9 + 8 k ) ( p σ k ) 4 / ( 9 + 8 k ) . (54) O_k(n + F_k(n,\sigma,p)) \text{ edges}, \qquad F_k(n,\sigma,p) = n^{(8+8k)/(9+8k)}(p\sigma^k)^{4/(9+8k)}. \tag*{(54)} O k ( n + F k ( n , σ , p )) edges , F k ( n , σ , p ) = n ( 8 + 8 k ) / ( 9 + 8 k ) ( p σ k ) 4/ ( 9 + 8 k ) . (54)
In particular, for k = 1 , 2 , 3 k = 1,2,3 k = 1 , 2 , 3 the nonlinear terms are n 16 / 17 ( p σ ) 4 / 17 n^{16/17}(p\sigma)^{4/17} n 16/17 ( p σ ) 4/17 , n 24 / 25 ( p σ 2 ) 4 / 25 n^{24/25}(p\sigma^2)^{4/25} n 24/25 ( p σ 2 ) 4/25 , and n 32 / 33 ( p σ 3 ) 4 / 33 n^{32/33}(p\sigma^3)^{4/33} n 32/33 ( p σ 3 ) 4/33 , respectively, with the ranges in Table 1 . No additional restriction p ≤ n p \le n p ≤ n is needed.
Proof. Extend the definition of F k F_k F k to k = 0 k = 0 k = 0 ; then (52) is the induction base, valid for p ≤ n p \le n p ≤ n . Assume k ≥ 1 k \ge1 k ≥ 1 . The case p ≤ n p \le\sqrt{n} p ≤ n follows from (53). Otherwise put
a = 9 + 8 k , M = p σ k , d = n − 1 / a M 4 / a > 1. a = 9 + 8k,\qquad M = p\sigma^k,\qquad d = n^{-1/a}M^{4/a} > 1. a = 9 + 8 k , M = p σ k , d = n − 1/ a M 4/ a > 1.
Apply Lemma 34(i) and construct a + 2 ( k − 1 ) +2(k-1) + 2 ( k − 1 ) spanner for all reachable pairs in S × R S \times R S × R . If their number is q q q , then
q σ k − 1 ≤ M / d 2 = n 2 / a M ( a − 8 ) / a ≤ n 1 + 2 ( k − 1 ) / 3 . q\sigma^{k-1} \le M/d^2 = n^{2/a}M^{(a-8)/a} \le n^{1+2(k-1)/3}. q σ k − 1 ≤ M / d 2 = n 2/ a M ( a − 8 ) / a ≤ n 1 + 2 ( k − 1 ) /3 .
Indeed, substituting M ≤ n 1 + 2 k / 3 M \le n^{1+2k/3} M ≤ n 1 + 2 k /3 into the middle expression gives n ( 2 k + 1 ) / 3 = n 1 + 2 ( k − 1 ) / 3 n^{(2k+1)/3} = n^{1+2(k-1)/3} n ( 2 k + 1 ) /3 = n 1 + 2 ( k − 1 ) /3 . Thus the induction hypothesis applies to the auxiliary demands, including q ≤ n q \le n q ≤ n when k = 1 k = 1 k = 1 . If no auxiliary demand is reachable, the empty auxiliary subgraph suffices. Since d a = M 4 / n d^a = M^4/n d a = M 4 / n , its nonlinear cost satisfies
F k − 1 ( n , σ , q ) ≤ n 8 k / ( 8 k + 1 ) ( M / d 2 ) 4 / ( 8 k + 1 ) = n d . F_{k-1}(n,\sigma,q) \le n^{8k/(8k+1)}(M/d^2)^{4/(8k+1)} = nd. F k − 1 ( n , σ , q ) ≤ n 8 k / ( 8 k + 1 ) ( M / d 2 ) 4/ ( 8 k + 1 ) = n d .
The auxiliary linear term O k ( n ) O_k(n) O k ( n ) is absorbed by O k ( n d ) O_k(nd) O k ( n d ) , since d > 1 d > 1 d > 1 . Also n d = F k ( n , σ , p ) nd = F_k(n,\sigma,p) n d = F k ( n , σ , p ) . The sampling step adds two to the error, so at least half the demands have additive error 2 k 2k 2 k at this cost. For fixed n n n , σ \sigma σ , k k k , the function F k F_k F k is proportional to p 4 / ( 9 + 8 k ) p^{4/(9+8k)} p 4/ ( 9 + 8 k ) , and the range p σ k ≤ n 1 + 2 k / 3 p\sigma^k \le n^{1+2k/3} p σ k ≤ n 1 + 2 k /3 persists on demand subsets. Therefore Lemma 35 completes the induction. Only the level-zero auxiliary calls require at most n n n pairs; the final exact completion uses at most n \sqrt{n} n pairs.
Lemma 38 (Classical-input source-sensitive bounds). For every fixed integer k ≥ 0 k \ge0 k ≥ 0 and P ⊆ S × V P \subseteq S \times V P ⊆ S × V , there is an additive + 2 k +2k + 2 k spanner with
O k ( n + C k ( n , σ , p ) ) edges , C k ( n , σ , p ) = n 1 − 1 / ( 4 k + 2 ) ( p σ k ) 1 / ( 2 k + 1 ) . O_k(n + C_k(n,\sigma,p))\ \text{edges},\qquad C_k(n,\sigma,p) = n^{1-1/(4k+2)}(p\sigma^k)^{1/(2k+1)}. O k ( n + C k ( n , σ , p )) edges , C k ( n , σ , p ) = n 1 − 1/ ( 4 k + 2 ) ( p σ k ) 1/ ( 2 k + 1 ) . There is also such a spanner with O k ( n + n ( p σ k ) 1 / ( 2 k + 3 ) ) O_k(n + n(p\sigma^k)^{1/(2k+3)}) O k ( n + n ( p σ k ) 1/ ( 2 k + 3 ) ) edges when p σ k ≤ n 1 + 2 k / 3 p\sigma^k \le n^{1+2k/3} p σ k ≤ n 1 + 2 k /3 .
Proof. For the first bound, induct on k k k . The base k = 0 k = 0 k = 0 is C 0 ( n , σ , p ) = n p C_0(n,\sigma,p) = \sqrt{n}\,p C 0 ( n , σ , p ) = n p , supplied by (53) without a restriction on p p p . Suppose k ≥ 1 k \ge1 k ≥ 1 and p > n p > \sqrt{n} p > n , write M = p σ k M = p\sigma^k M = p σ k , and choose d = n − 1 / ( 4 k + 2 ) M 1 / ( 2 k + 1 ) > 1 d = n^{-1/(4k+2)}M^{1/(2k+1)} > 1 d = n − 1/ ( 4 k + 2 ) M 1/ ( 2 k + 1 ) > 1 . Apply Lemma 34(i). If q q q is the number of reachable auxiliary pairs in S × R S \times R S × R , then q σ k − 1 ≤ M / d 2 q\sigma^{k-1} \le M/d^2 q σ k − 1 ≤ M / d 2 . The induction hypothesis and d 2 k + 1 = M / n d^{2k+1} = M/\sqrt{n} d 2 k + 1 = M / n give
C k − 1 ( n , σ , q ) ≤ n 1 − 1 / ( 4 k − 2 ) ( M / d 2 ) 1 / ( 2 k − 1 ) = n d . C_{k-1}(n,\sigma,q) \le n^{1-1/(4k-2)}(M/d^2)^{1/(2k-1)} = nd. C k − 1 ( n , σ , q ) ≤ n 1 − 1/ ( 4 k − 2 ) ( M / d 2 ) 1/ ( 2 k − 1 ) = n d .
Consequently, an additive + 2 ( k − 1 ) +2(k-1) + 2 ( k − 1 ) auxiliary spanner and the sampling subgraph together satisfy half the demands with error 2 k 2k 2 k and cost O k ( n d ) O_k(nd) O k ( n d ) . Since n d = C k ( n , σ , p ) nd = C_k(n,\sigma,p) n d = C k ( n , σ , p ) is a positive power of p p p , Lemma 35 proves the first bound. There is no restriction on the exact auxiliary demand count.
For the second bound, the base k = 0 k = 0 k = 0 is the exact-preserver theorem of [15 ] , which gives O ( n 2 / 3 q 2 / 3 + n q 1 / 3 ) = O ( n q 1 / 3 ) O(n^{2/3}q^{2/3} + nq^{1/3}) = O(nq^{1/3}) O ( n 2/3 q 2/3 + n q 1/3 ) = O ( n q 1/3 ) for 1 ≤ q ≤ n 1 \le q \le n 1 ≤ q ≤ n . For k ≥ 1 k \ge1 k ≥ 1 and p > n p > \sqrt{n} p > n , choose d = M 1 / ( 2 k + 3 ) > 1 d = M^{1/(2k+3)} > 1 d = M 1/ ( 2 k + 3 ) > 1 and again apply Lemma 34(i). The auxiliary product satisfies
q σ k − 1 ≤ M / d 2 = M ( 2 k + 1 ) / ( 2 k + 3 ) ≤ n ( 2 k + 1 ) / 3 = n 1 + 2 ( k − 1 ) / 3 , q\sigma^{k-1} \le M/d^2 = M^{(2k+1)/(2k+3)} \le n^{(2k+1)/3} = n^{1+2(k-1)/3}, q σ k − 1 ≤ M / d 2 = M ( 2 k + 1 ) / ( 2 k + 3 ) ≤ n ( 2 k + 1 ) /3 = n 1 + 2 ( k − 1 ) /3 ,
so the induction hypothesis applies, including the base's q ≤ n q \le n q ≤ n condition when k = 1 k = 1 k = 1 . Its nonlinear cost is at most n ( M / d 2 ) 1 / ( 2 k + 1 ) = n d n(M/d^2)^{1/(2k+1)} = nd n ( M / d 2 ) 1/ ( 2 k + 1 ) = n d . The linear term is absorbed since d > 1 d > 1 d > 1 . The sampling step therefore satisfies half the demands with error 2 k 2k 2 k at cost O k ( n d ) O_k(nd) O k ( n d ) . The range persists on demand subsets and n d = n ( p σ k ) 1 / ( 2 k + 3 ) nd = n(p\sigma^k)^{1/(2k+3)} n d = n ( p σ k ) 1/ ( 2 k + 3 ) is a positive power of p p p , allowing Lemma 35. In both inductions, the cases p ≤ n p \le\sqrt{n} p ≤ n are handled directly by (53). ▫
Complete sourcewise bounds
Lemma 39 (Clustering reduction). For every integer Δ ≥ 1 \Delta\ge1 Δ ≥ 1 there are J 0 ⊆ G J_0 \subseteq G J 0 ⊆ G and R ⊆ V R \subseteq V R ⊆ V with ∣ E ( J 0 ) ∣ = O ( n Δ ) |E(J_0)| = O(n\Delta) ∣ E ( J 0 ) ∣ = O ( n Δ ) and ∣ R ∣ ≤ n / Δ |R| \le n/\Delta ∣ R ∣ ≤ n /Δ such that the following holds for every source set S S S . Adjoining any additive + β +\beta + β spanner for the reachable pairs in S × R S \times R S × R produces a complete sourcewise additive + ( β + 2 ) +(\beta+ 2) + ( β + 2 ) spanner.
Proof. Initially all vertices are unclustered. While a vertex has at least Δ \Delta Δ unclustered neighbors, select exactly Δ \Delta Δ of them as a cluster, assign this vertex as their center, and mark these neighbors clustered. A center need not itself be unclustered and may be reused. Let R R R be the set of centers, so ∣ R ∣ ≤ n / Δ |R| \le n/\Delta ∣ R ∣ ≤ n /Δ . Keep all cluster-star edges, at most n n n in total, and every edge incident to the final unclustered set U U U . At termination ∣ N G ( v ) ∩ U ∣ < Δ |N_G(v) \cap U| < \Delta ∣ N G ( v ) ∩ U ∣ < Δ for every v v v , so these latter edges number at most ∑ v ∣ N G ( v ) ∩ U ∣ < n Δ \sum_v |N_G(v) \cap U| < n\Delta ∑ v ∣ N G ( v ) ∩ U ∣ < n Δ . Let J 0 J_0 J 0 be their union.
For a reachable ( s , t ) ∈ S × V (s,t) \in S \times V ( s , t ) ∈ S × V , choose any shortest s s s –t t t path π ( s , t ) \pi(s,t) π ( s , t ) in G G G and traverse it from s s s to t t t . If it is contained in J 0 J_0 J 0 , it is already preserved. Otherwise let v v v be the head of its last missing edge. Both endpoints of that edge are clustered, since every edge incident to an unclustered vertex was retained. In particular, v v v is clustered, and the subpath from v v v to t t t lies in J 0 J_0 J 0 by the choice of the last missing edge. If z ∈ R z \in R z ∈ R is its center, the auxiliary s s s –z z z route, the edge z v zv z v , and this suffix have total length at most
dist G ( s , z ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 2. \operatorname{dist}_G(s,z) + \beta+ 1 + \operatorname{dist}_G(v,t) \le\operatorname{dist}_G(s,t) + \beta+ 2. dist G ( s , z ) + β + 1 + dist G ( v , t ) ≤ dist G ( s , t ) + β + 2.
Here dist G ( s , z ) ≤ dist G ( s , v ) + 1 \operatorname{dist}_G(s,z) \le\operatorname{dist}_G(s,v) + 1 dist G ( s , z ) ≤ dist G ( s , v ) + 1 , because z v ∈ E zv \in E z v ∈ E , and the chosen path gives dist G ( s , v ) + dist G ( v , t ) = dist G ( s , t ) \operatorname{dist}_G(s,v) + \operatorname{dist}_G(v,t) = \operatorname{dist}_G(s,t) dist G ( s , v ) + dist G ( v , t ) = dist G ( s , t ) . The path can be chosen independently for each pair, and the same J 0 J_0 J 0 and R R R work for every source set S S S .
Theorem 40 (Complete sourcewise bounds). For every fixed integer k ≥ 2 k \ge2 k ≥ 2 and source set S S S of size σ ≤ n ( 2 k − 1 ) / ( 3 k ) \sigma\le n^{(2k-1)/(3k)} σ ≤ n ( 2 k − 1 ) / ( 3 k ) , there is a complete sourcewise additive + 2 k +2k + 2 k spanner with
O k ( n + n ( 8 + 8 k ) / ( 5 + 8 k ) σ 4 k / ( 5 + 8 k ) ) O_k\left(n + n^{(8+8k)/(5+8k)}\sigma^{4k/(5+8k)}\right) O k ( n + n ( 8 + 8 k ) / ( 5 + 8 k ) σ 4 k / ( 5 + 8 k ) ) edges. For k = 2 k = 2 k = 2 this gives O ( n + n 8 / 7 σ 8 / 21 ) O(n + n^{8/7}\sigma^{8/21}) O ( n + n 8/7 σ 8/21 ) edges when σ ≤ n 1 / 2 \sigma\le n^{1/2} σ ≤ n 1/2 . For k = 3 k = 3 k = 3 it gives O ( n + n 32 / 29 σ 12 / 29 ) O(n + n^{32/29}\sigma^{12/29}) O ( n + n 32/29 σ 12/29 ) edges when σ ≤ n 5 / 9 \sigma\le n^{5/9} σ ≤ n 5/9 .
Proof. Set d = n 3 / ( 8 k + 5 ) σ 4 k / ( 8 k + 5 ) d = n^{3/(8k+5)}\sigma^{4k/(8k+5)} d = n 3/ ( 8 k + 5 ) σ 4 k / ( 8 k + 5 ) and Δ = ⌈ d ⌉ \Delta= \lceil d \rceil Δ = ⌈ d ⌉ . Use Lemma 39 and apply Theorem 37 at level k − 1 k - 1 k − 1 to the reachable pairs in S × R S \times R S × R . Their count q ≤ n σ / Δ q \le n\sigma/\Delta q ≤ nσ /Δ satisfies
q σ k − 1 ≤ n σ k / d ≤ n 1 + 2 ( k − 1 ) / 3 , q\sigma^{k-1} \le n\sigma^k/d \le n^{1+2(k-1)/3}, q σ k − 1 ≤ n σ k / d ≤ n 1 + 2 ( k − 1 ) /3 ,
where the last inequality follows from the assumed bound on σ \sigma σ . The auxiliary nonlinear cost is at most
F k − 1 ( n , σ , q ) ≤ n 8 k / ( 8 k + 1 ) ( n σ k / d ) 4 / ( 8 k + 1 ) = n d . F_{k-1}(n,\sigma,q) \le n^{8k/(8k+1)}(n\sigma^k/d)^{4/(8k+1)} = nd. F k − 1 ( n , σ , q ) ≤ n 8 k / ( 8 k + 1 ) ( n σ k / d ) 4/ ( 8 k + 1 ) = n d .
The equality in the last display follows from d 8 k + 5 = n 3 σ 4 k d^{8k+5} = n^3\sigma^{4k} d 8 k + 5 = n 3 σ 4 k . The auxiliary linear term is O k ( n ) O_k(n) O k ( n ) . The clustering cost is O ( n Δ ) = O ( n + n d ) O(n\Delta) = O(n + nd) O ( n Δ ) = O ( n + n d ) , and its attachment adds two to the auxiliary error 2 ( k − 1 ) 2(k - 1) 2 ( k − 1 ) . Thus the final error is 2 k 2k 2 k ; substituting d d d into n d nd n d proves the stated edge bound.
Corollary 41 (A classical-input sourcewise bound). For every source set S S S of size σ \sigma σ , there is a complete sourcewise additive + 6 +6 + 6 spanner with O ( n + n 13 / 12 σ 1 / 2 ) O(n + n^{13/12}\sigma^{1/2}) O ( n + n 13/12 σ 1/2 ) edges.
Proof. Take Δ = ⌈ n 1 / 12 σ 1 / 2 ⌉ \Delta= \lceil n^{1/12}\sigma^{1/2} \rceil Δ = ⌈ n 1/12 σ 1/2 ⌉ in Lemma 39. Apply the first bound of Lemma 38 with k = 2 k = 2 k = 2 to S × R S \times R S × R . Since q ≤ n σ / Δ q \le n\sigma/\Delta q ≤ nσ /Δ , its nonlinear cost is
C 2 ( n , σ , q ) = n 9 / 10 ( q σ 2 ) 1 / 5 ≤ n 11 / 10 σ 3 / 5 Δ − 1 / 5 ≤ n 13 / 12 σ 1 / 2 . C_2(n,\sigma,q) = n^{9/10}(q\sigma^2)^{1/5} \le n^{11/10}\sigma^{3/5}\Delta^{-1/5} \le n^{13/12}\sigma^{1/2}. C 2 ( n , σ , q ) = n 9/10 ( q σ 2 ) 1/5 ≤ n 11/10 σ 3/5 Δ − 1/5 ≤ n 13/12 σ 1/2 .
The clustering cost has the same bound, up to O ( n ) O(n) O ( n ) , and the error is $4 + 2 = 6.
Comparing the two complete-sourcewise + 6 +6 + 6 bounds, we have
n 32 / 29 σ 12 / 29 n 13 / 12 σ 1 / 2 = n 7 / 348 σ − 5 / 58 . \frac{n^{32/29}\sigma^{12/29}}{n^{13/12}\sigma^{1/2}}=n^{7/348}\sigma^{-5/58}. n 13/12 σ 1/2 n 32/29 σ 12/29 = n 7/348 σ − 5/58 .
Thus, for σ = n a \sigma=n^a σ = n a with fixed 7 / 30 < a < 14 / 31 7/30<a<14/31 7/30 < a < 14/31 , the k = 3 k=3 k = 3 bound of Theorem 40 gives a strict polynomial improvement over both Corollary 41 and the previous bounds listed in Table 1 .
Classical comparison terms in Table 1 . The source-sensitive CE and BW terms follow by setting k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 in Lemma 38 . The pairwise + 4 +4 + 4 term O ( n + n 9 / 10 p 2 / 5 ) O(n+n^{9/10}p^{2/5}) O ( n + n 9/10 p 2/5 ) also follows from Lemma 34 (ii) using (53) and d = n − 1 / 10 p 2 / 5 d=n^{-1/10}p^{2/5} d = n − 1/10 p 2/5 , followed by Lemma 35. The complete-sourcewise + 6 +6 + 6 term O ( n + n 15 / 14 σ 4 / 7 ) O(n+n^{15/14}\sigma^{4/7}) O ( n + n 15/14 σ 4/7 ) follows directly from the first bound of Lemma 38 with k = 3 k=3 k = 3 and p ≤ n σ p\le n\sigma p ≤ nσ , since
C 3 ( n , σ , p ) ≤ n 13 / 14 ( n σ ⋅ σ 3 ) 1 / 7 = n 15 / 14 σ 4 / 7 . C_3(n,\sigma,p)\le n^{13/14}(n\sigma\cdot\sigma^3)^{1/7}=n^{15/14}\sigma^{4/7}. C 3 ( n , σ , p ) ≤ n 13/14 ( nσ ⋅ σ 3 ) 1/7 = n 15/14 σ 4/7 .
This bound applies to every source set and uses (53) through three levels of the sampling reduction, with constant-fraction completion at each level. For the remaining two derived partial-demand comparisons, use Lemma 34 (i). The subset + 2 +2 + 2 theorem [12 ] supplies a spanner for T × T T\times T T × T with O ( n ∣ T ∣ ) O(n\sqrt{|T|}) O ( n ∣ T ∣ ) edges. Applying it to T = S ∪ R T=S\cup R T = S ∪ R costs
O ( n σ + p / d 2 ) . O\left(n\sqrt{\sigma+p/d^2}\right). O ( n σ + p / d 2 ) .
With d = max { σ 1 / 2 , p 1 / 4 } d=\max\{\sigma^{1/2},p^{1/4}\} d = max { σ 1/2 , p 1/4 } this is O ( n d ) O(nd) O ( n d ) . Keep d d d fixed and repeat on the unsatisfied demands until at most n \sqrt{n} n remain, then finish with (53). Since the number of demand pairs is at most n 2 n^2 n 2 , there are O ( log n ) O(\log n) O ( log n ) rounds. This gives the + 4 +4 + 4 comparison bound with O ~ ( n d ) \widetilde O(nd) O ( n d ) edges.
For the + 6 +6 + 6 comparison, use the rectangular + 4 +4 + 4 theorem of [26 ] . Its auxiliary cost is O ( n ( σ ∣ R ∣ ) 1 / 4 ) O(n(\sigma|R|)^{1/4}) O ( n ( σ ∣ R ∣ ) 1/4 ) . Taking d = ( σ p ) 1 / 6 d=(\sigma p)^{1/6} d = ( σ p ) 1/6 bounds this cost by O ( n d ) O(nd) O ( n d ) ; Lemma 35 gives O ( n + n ( σ p ) 1 / 6 ) O(n+n(\sigma p)^{1/6}) O ( n + n ( σ p ) 1/6 ) edges. In these applications p ≤ n p\le\sqrt n p ≤ n is handled directly by (53).
Acknowledgments
Acknowledgments. We thank Greg Bodwin for helpful discussions at the early stage of the project. We also thank the anonymous reviewers for their helpful feedback and for pointing out potential new research directions.
AI methodology statement
AI methodology statement. We used ChatGPT 6-Astra to assist in developing the results in § 7 and § 8 . All work concerning Theorem 1 , including its development and proof, was carried out entirely by the authors without AI assistance. The authors wrote the entire paper and take full responsibility for all of its contents, including the correctness of the results and proofs.
Remaining Proofs
Proof of Lemma 4. We adapt the distance-difference argument of [15 ] , using essential edges to handle an arbitrary minimal distance preserver. For every demand q = ( s , t ) ∈ P q=(s,t)\in P q = ( s , t ) ∈ P , fix a shortest path π ( q ) \pi(q) π ( q ) in H H H , directed from s s s to t t t . Since H H H preserves the demand distances, each π ( q ) \pi(q) π ( q ) is also a shortest path in G G G . By minimality, choose a demand-label l ( e ) l(e) l ( e ) for every edge e ∈ E H e\in E_H e ∈ E H , and orient e e e as it appears on π ( l ( e ) ) \pi(l(e)) π ( l ( e )) . We call the source of l ( e ) l(e) l ( e ) the source of the oriented edge e e e .
If an edge e = ( a , x ) e=(a,x) e = ( a , x ) has source u u u , then dist H ( u , x ) = dist G ( u , x ) \operatorname{dist}_H(u,x)=\operatorname{dist}_G(u,x) dist H ( u , x ) = dist G ( u , x ) , and every shortest u u u –x x x path in H H H ends with e e e . Indeed, the prefix of π ( l ( e ) ) \pi(l(e)) π ( l ( e )) ending at x x x proves the distance equality. Any shortest u u u –x x x path avoiding e e e could replace this prefix, contradicting that e e e is essential to l ( e ) l(e) l ( e ) . Consequently, at most one edge with a given source enters any vertex.
Fix a demand q = ( s , t ) ∈ P q=(s,t)\in P q = ( s , t ) ∈ P and a source u ∈ S u\in S u ∈ S . Let F ( q , u ) F(q,u) F ( q , u ) consist of the edges with source u u u entering a vertex of π ( q ) \pi(q) π ( q ) , other than the edge preceding that vertex on π ( q ) \pi(q) π ( q ) . We claim that
∣ F ( q , u ) ∣ ≤ 2 ⌊ d ⌋ + 1. |F(q,u)|\le2\lfloor d\rfloor+1. ∣ F ( q , u ) ∣ ≤ 2 ⌊ d ⌋ + 1.
For each head x x x of an edge in F ( q , u ) F(q,u) F ( q , u ) , define
Δ ( x ) = dist G ( u , x ) − dist G ( s , x ) . \Delta(x)=\operatorname{dist}_G(u,x)-\operatorname{dist}_G(s,x). Δ ( x ) = dist G ( u , x ) − dist G ( s , x ) .
The triangle inequality in G G G gives − d ≤ Δ ( x ) ≤ d -d\le\Delta(x)\le d − d ≤ Δ ( x ) ≤ d , so there are at most 2 ⌊ d ⌋ + 1 2\lfloor d\rfloor+1 2 ⌊ d ⌋ + 1 possible integer values. Suppose two distinct heads x , y x,y x , y have the same value, with x x x preceding y y y on π ( q ) \pi(q) π ( q ) . Writing ∣ π ( q ) [ x , y ] ∣ |\pi(q)[x,y]| ∣ π ( q ) [ x , y ] ∣ for the length of the subpath from x x x to y y y , we have
dist G ( u , x ) + ∣ π ( q ) [ x , y ] ∣ = dist G ( u , y ) . \operatorname{dist}_G(u,x)+|\pi(q)[x,y]|=\operatorname{dist}_G(u,y). dist G ( u , x ) + ∣ π ( q ) [ x , y ] ∣ = dist G ( u , y ) .
A shortest u u u –x x x path in H H H followed by π ( q ) [ x , y ] \pi(q)[x,y] π ( q ) [ x , y ] is therefore a shortest u u u –y y y path in H H H . It avoids the edge f ∈ F ( q , u ) f\in F(q,u) f ∈ F ( q , u ) entering y y y : the first part has length strictly less than dist G ( u , y ) \operatorname{dist}_G(u,y) dist G ( u , y ) and hence cannot visit y y y , while the second part does not contain f f f , since f f f is not the predecessor edge at y y y on π ( q ) \pi(q) π ( q ) . This contradicts the preceding property of f f f and proves the claim.
Let deg H i n ( x ) \deg^{\mathrm{in}}_H(x) deg H in ( x ) be the indegree in this orientation, and set
b = ∑ x ∈ V H ( deg H i n ( x ) 2 ) . b=\sum_{x\in V_H}\binom{\deg^{\mathrm{in}}_H(x)}{2}. b = x ∈ V H ∑ ( 2 deg H in ( x ) ) .
Fix a total ordering of E H E_H E H . For each pair of distinct edges e , f e,f e , f entering the same vertex, with e e e preceding f f f in this ordering, charge the pair to ( l ( e ) , u , f ) (l(e),u,f) ( l ( e ) , u , f ) , where u u u is the source of f f f . The edge e e e is the predecessor edge on π ( l ( e ) ) \pi(l(e)) π ( l ( e )) at their common head, so f ∈ F ( l ( e ) , u ) f\in F(l(e),u) f ∈ F ( l ( e ) , u ) . This charge is injective, since l ( e ) l(e) l ( e ) and the head of f f f uniquely determine e e e . Thus
b ≤ ∑ q ∈ P ∑ u ∈ S ∣ F ( q , u ) ∣ ≤ p σ ( 2 ⌊ d ⌋ + 1 ) . b\le\sum_{q\in P}\sum_{u\in S}|F(q,u)|\le p\sigma(2\lfloor d\rfloor+1). b ≤ q ∈ P ∑ u ∈ S ∑ ∣ F ( q , u ) ∣ ≤ p σ ( 2 ⌊ d ⌋ + 1 ) .
If σ ≥ 2 \sigma\ge2 σ ≥ 2 , then d ≥ 1 d\ge1 d ≥ 1 and hence b = O ( p σ d ) b=O(p\sigma d) b = O ( p σ d ) . If σ = 1 \sigma=1 σ = 1 , every vertex has indegree at most one, so b = 0 b=0 b = 0 ; in particular, the same bound holds when d = 0 d=0 d = 0 .
Finally, restrict the orientation to H [ U ] H[U] H [ U ] , and write m = ∣ E H U ∣ m = |E_{H}^{U}| m = ∣ E H U ∣ and a x = deg H [ U ] i n ( x ) a_x = \deg_{H[U]}^{\mathrm{in}}(x) a x = deg H [ U ] in ( x ) . The case k = 0 k = 0 k = 0 is immediate. Otherwise, by Cauchy–Schwarz,
m 2 = ( ∑ x ∈ U a x ) 2 ≤ k ∑ x ∈ U a x 2 = k ( m + 2 ∑ x ∈ U ( a x 2 ) ) ≤ k ( m + 2 b ) . m^2 = \left(\sum_{x \in U} a_x\right)^2 \le k \sum_{x \in U} a_x^2 = k\left(m + 2\sum_{x \in U} \binom{a_x}{2}\right) \le k(m + 2b). m 2 = ( x ∈ U ∑ a x ) 2 ≤ k x ∈ U ∑ a x 2 = k ( m + 2 x ∈ U ∑ ( 2 a x ) ) ≤ k ( m + 2 b ) .
It follows that
∣ E H U ∣ = m ≤ k + 2 k b = O ( k + k p σ d ) , |E_{H}^{U}| = m \le k + \sqrt{2kb} = O\left(k + \sqrt{kp\sigma d}\right), ∣ E H U ∣ = m ≤ k + 2 k b = O ( k + k p σ d ) ,
as desired.