Lower Bounds for Additive Spanners, Emulators, and More
David P. Woodruff · 2006
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 deltaH(u, v) les deltaG(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)n1 + 1k/) 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 deltaG(u, v) ges deltaG(u, v) ges deltaG(u, v) + d. We show a lower bound of Omega((1/k2)n1 + 1k/) 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 n1k + c/ for any c ges 0, we prove a bound of Omega((1/k)n1 + 1k - c(1 + 2/(k - 1))/) for additive spanners and Omega((1/k2)n1 + 1k - 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