论文标题
史诗般的失败：模拟器可以免费耐受多个边缘故障
Epic Fail: Emulators can tolerate polynomially many edge faults for free
论文作者
论文摘要
图$ g $的$ t $ emulator是一个图$ h $，近似于其成对最短路径距离，直至乘法$ t $错误。我们研究了Bodwin，Dinitz和Nazari [ITCS 2022]最近引入的模型，研究了容错的$ t $ emulators，以实现顶点故障。在本文中，我们考虑了边缘故障的版本，并表明它们表现出令人惊讶的不同行为。 特别是，我们的主要结果是，对于$（2K-1）$ - 带有$ k $奇数的仿真器，我们可以免费容忍多项式的边缘故障。例如：对于任何$ n $ -Node输入图，我们在$ O（n^{4/3}）上构造了$ 5 $ - emulator（$ k = 3 $）$ edge of to $ f = o（n^{2/9}）$ edge Fults。众所周知，即使$ 5 $ - emulator不需要容忍任何故障，$ω（n^{4/3}）$边缘也是必要的。因此，我们不需要支付额外的费用来获得这种容忍度。对于奇数$ k $，我们留下了确切的自由容忍度的精确范围，以及是否可以证明类似的现象甚至可以证明$ k $。
A $t$-emulator of a graph $G$ is a graph $H$ that approximates its pairwise shortest path distances up to multiplicative $t$ error. We study fault tolerant $t$-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for $(2k-1)$-emulators with $k$ odd, we can tolerate a polynomial number of edge faults for free. For example: for any $n$-node input graph, we construct a $5$-emulator ($k=3$) on $O(n^{4/3})$ edges that is robust to $f = O(n^{2/9})$ edge faults. It is well known that $Ω(n^{4/3})$ edges are necessary even if the $5$-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd $k$, and whether a similar phenomenon can be proved for even $k$.
