New Additive Emulators

For a given (possibly weighted) graph G = (V,E), an additive emulator H is a weighted graph in V × V that preserves the (all pairs) G-distances up to a small additive stretch. In their breakthrough result, [Abboud and Bodwin, STOC 2016] ruled out the possibility of obtaining o(n^{4/3})-size emulator with n^{o(1)} additive stretch. The focus of our paper is in the following question that has been explicitly stated in many of the prior work on this topic: What is the minimal additive stretch attainable with linear size emulators? The only known upper bound for this problem is given by an implicit construction of [Pettie, ICALP 2007] that provides a linear-size emulator with +Õ(n^{1/4}) stretch. No improvement on this problem has been shown since then. In this work we improve upon the long standing additive stretch of Õ(n^{1/4}), by presenting constructions of linear-size emulators with Õ(n^{0.222}) additive stretch. Our constructions improve the state-of-the-art size vs. stretch tradeoff in the entire regime. For example, for every ε > 1/7, we provide +n^{f(ε)} emulators of size Õ(n^{1+ε}), for f(ε) = 1/5-3ε/5. This should be compared with the current bound of f(ε) = 1/4-3ε/4 by [Pettie, ICALP 2007]. The new emulators are based on an extended and optimized toolkit for computing weighted additive emulators with sublinear distance error. Our key construction provides a weighted modification of the well-known Thorup and Zwick emulators [SODA 2006]. We believe that this TZ variant might be of independent interest, especially for providing improved stretch for distant pairs.