论文标题
在啤酒花中拥有希望：新的跨越，保存器和啤酒花的下限
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
论文作者
论文摘要
求产品和跨度是基本的图形结构，在最短路径计算，分布式通信等中发挥关键作用。给定图$ g $的（近乎外观）的跳动是一个（小）加权边缘的子集$ h $，当添加到图形$ g $中时，它会减少最短路径的啤酒花（边缘）数量（边缘）。另一方面，跨越和距离保存器要求从图中删除许多边缘，同时大约保留了最短的路径距离。 我们提供从图形集体到已知的指标压缩方案的一般还原方案。因此，我们为后者获得了新的和改进的上限结构，以及霍普斯的新下限结果。我们的工作在诱人的开放问题上取得了重大进展，即霍普斯和跨越跨越的正式联系，例如，如埃尔金和内曼[Bull》中提出的。 EATCS 2020]。
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph $G$ is a (small) subset of weighted edges $H$ that when added to the graph $G$ reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path distances. We provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our work makes a significant progress on the tantalizing open problem concerning the formal connection between hopsets and spanners, e.g., as posed by Elkin and Neiman [Bull. EATCS 2020].
