2021/10/29 by Kevin Lü, Lu, Kevin, Virginia Vassilevska Williams +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2110.15809
openalex publication_date 2021/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(n1/11) to Ω(n2/21). For O(n)-sized emulators, we improve the lower bound on the additive stretch from Ω(n1/18) to Ω(n1/16). For O(m)-sized shortcut sets, we improve the lower bound on the graph diameter from Ω(n1/11) to Ω(n1/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.