Lower Bounds for Additive Spanners, Emulators, and More

An additive spanner of an unweighted undirected graph G with distortion d is a subgraph H such that for any two vertices u,v isin G, we have delta
_H
(u, v) les delta
_G
(u, v) + d. For every k = O((ln n)/( ln ln n)), we construct a graph G on vertices for which any additive spanner of G with distortion 2k - 1 has Omega((1/k)n
^{1 + 1}
k/) edges. This matches the lower bound previously known only to hold under a 1963 conjecture of Erdos. We generalize our lower bound in a number of ways. First, we consider graph emulators introduced by Dor, Halperin, and Zwick (FOCS, 1996), where an emulator of an unweighted undirected graph G with distortion d is like an additive spanner except H may be an arbitrary weighted graph such that delta
_G
(u, v) ges delta
_G
(u, v) ges delta
_G
(u, v) + d. We show a lower bound of Omega((1/k
²
)n
^{1 + 1}
k/) edges for distortion- (2k - 1) emulators. These are the first non-trivial bounds for k > 3. Second, we parameterize our bounds in terms of the minimum degree of the graph. Namely, for minimum degree n
¹
k + c/ for any c ges 0, we prove a bound of Omega((1/k)n
^{1 + 1}
k - c(1 + 2/(k - 1))/) for additive spanners and Omega((1/k
²
)n
^{1 + 1}
k - c(1 + 2/(k - 1))/) for emulators. For k = 2 these can be improved to OmegaQ(n
^{(3/2) - c}
). This partially answers a question of Baswana et al. (SODA, 2005) for additive spanners. Finally, we continue the study of pair-wise and source-wise distance preservers defined by Coppersmith and Elkin (SODA, 2005) by considering their approximate variants and their relaxation to emulators. We prove the first lower bounds for such graphs