论文标题
近乎添加的跨度和近乎脱落的啤酒花，统一的视图
Near-Additive Spanners and Near-Exact Hopsets, A Unified View
论文作者
论文摘要
给定一个{\ em未加权}的无向图$ g =（v，e）$和一对参数$ε> 0 $，$β= 1,2，\ ldots $，a子graph $ g'=（v，h）$，$ h \ h \ sebseteq e $，$ g $ as $ g $ as a { {\ em近添加剂}）$ g $，如果对于每个$ u，v $，$$ d_ d_ {g'}（u，v）\ le（1 +ε）d_g（u，v）d_g（u，v） + β〜。$。$。 1,2，\ ldots $，存在$（1+ε，β）$ - SPANNER $ g'$，带有$ o_ {ε，κ}（n^{1+1/κ}）$边缘，带有$β=β=β=β_{ep {ep} = \ weft（ 2}〜。$$此绑定仍然是最新的，并且其对$ε$的依赖（对于小$κ$的情况下）在\ cite {abp18}中被证明很紧。 给定一个{\ em加权}无向图$ g =（v，e，ω）$和一对参数$ε> 0 $，$β= 1,2，\ ldots $，a图$ g'=（v，h，ω'）$是a {\ em $ $ $ $（1+ε，β）$ - β） $ g $如果对于每个$ u，v $，$$ d_g（u，v）\ le d_ {g \ cup g'}^{（β）}（u，v）\ le（1+ε）d_g（u，v） $β$ - （HOP）在Union Graph $ g \ cup g'$中$ u $和$ v $之间的结合距离。在\ cite {en16}中显示，对于上述任何$ n $ vertex $ g $和$ε$和$κ$，都存在$（1+ε，β）$ - 带有$ \ tilde {o} {o}（o}（n^{1+1+1/κ}）$ EDGES，$ evge，$β= ep} $ eps $ epse。 \ cite {ep01}和\ cite {en16}的两个结果不仅非常相似，而且它们的证明技术也是如此。此外，Thorup-Zwick后来在\ cite {en19，hp17}中显示了近加性跨度\ cite {tz06}的构造，以提供类似的杂种（\ cite {tz06}）特性。 在这项调查中，我们探讨了这种有趣的现象，绘制用于这些结果的基本证明技术，并突出介绍开放的问题。
Given an {\em unweighted} undirected graph $G = (V,E)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a subgraph $G' =(V,H)$, $H \subseteq E$, of $G$ is a {\em $(1+ε,β)$-spanner} (aka, a {\em near-additive spanner}) of $G$ if for every $u,v \in V$, $$d_{G'}(u,v) \le (1+ε)d_G(u,v) + β~.$$ It was shown in \cite{EP01} that for any $n$-vertex $G$ as above, and any $ε> 0$ and $κ= 1,2,\ldots$, there exists a $(1+ε,β)$-spanner $G'$ with $O_{ε,κ}(n^{1+1/κ})$ edges, with $$β= β_{EP} = \left({{\log κ} \over ε}\right)^{\log κ- 2}~.$$ This bound remains state-of-the-art, and its dependence on $ε$ (for the case of small $κ$) was shown to be tight in \cite{ABP18}. Given a {\em weighted} undirected graph $G = (V,E,ω)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a graph $G'= (V,H,ω')$ is a {\em $(1+ε,β)$-hopset} (aka, a {\em near-exact hopset}) of $G$ if for every $u,v \in V$, $$d_G(u,v) \le d_{G\cup G'}^{(β)}(u,v) \le (1+ε)d_G(u,v)~,$$ where $ d_{G\cup G'}^{(β)}(u,v)$ stands for a $β$-(hop)-bounded distance between $u$ and $v$ in the union graph $G \cup G'$. It was shown in \cite{EN16} that for any $n$-vertex $G$ and $ε$ and $κ$ as above, there exists a $(1+ε,β)$-hopset with $\tilde{O}(n^{1+1/κ})$ edges, with $β= β_{EP}$. Not only the two results of \cite{EP01} and \cite{EN16} are strikingly similar, but so are also their proof techniques. Moreover, Thorup-Zwick's later construction of near-additive spanners \cite{TZ06} was also shown in \cite{EN19,HP17} to provide hopsets with analogous (to that of \cite{TZ06}) properties. In this survey we explore this intriguing phenomenon, sketch the basic proof techniques used for these results, and highlight open questions.
