Error amplification for pairwise spanner lower bounds
Amir Abboud, Greg Bodwin · Symposium on Discrete Algorithms · 2016
A pairwise spanner of a graph G = (V, E) and a pair P ⊆ V × V is a subgraph H that preserves all pairwise distances in P, up to some additive error term +β. When β = 0 the object is called a pairwise distance preserver.A large and growing body of work has considered upper bounds for these objects, but lower bounds have been elusive. The only known lower bound results are (1) Coppersmith and Elkin (SODA'05) against preservers, and (2) considerably weaker bounds by Woodruff (FOCS'06) against spanners.Our main result is an amplification theorem: we prove that lower bounds against pairwise distance preservers imply lower bounds against pairwise spanners. In other words, to prove lower bounds against any constant error spanners, it is enough to consider only subgraphs that are not allowed any error at all!We apply this theorem to obtain drastically improved lower bounds. Some of these include:• Linear size pairwise spanners with up to +(2k -- 1) error cannot span |P| = ω(n(1+k)/(3+k)) pairs. This is a large improvement over Woodruff's |P| = ω(n2--2/k) (|P| is now linear, rather than quadratic, as k gets large).• |E(H)| = Ω(n1+1/k) edges are required for a +(2k -- 1) spanner of |P| = Ω(n1+1/k) pairs - this is another large improvement over Woodruff's |P| = Ω(n2).• The first tight bounds for pairwise spanners: for +2 error and P = Θ(n3/2) we show that Θ(n3/2) edges are necessary and sufficient (this also reflects a new upper bound: we construct +2 pairwise spanners on O(n|P|1/3) edges, removing a log factor from a prior algorithm).We also show analogous improved lower bounds against subset spanners (where P = S × S for some node subset S), and the first lower bounds against D threshold spanners (where P is the set of node pairs at distance at least D).