Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
share
We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve the distances of a given graph. A shortcut set is a set of edges that when added to a directed graph, decreases its diameter. The previous best known lower bounds for these three structures are given by Huang and Pettie [SWAT 2018]. For O(n)-sized spanners, we improve the lower bound on the additive stretch from Ω(n^1/11) to Ω(n^2/21). For O(n)-sized emulators, we improve the lower bound on the additive stretch from Ω(n^1/18) to Ω(n^2/29). For O(m)-sized shortcut sets, we improve the lower bound on the graph diameter from Ω(n^1/11) to Ω(n^1/8). Our key technical contribution, which is the basis of all of our bounds, is an improvement of a graph product known as an alternation product.
READ FULL TEXT