



















We initiate the study on fault-tolerant spanners in hypergraphs and develop fast algorithms for their constructions. A fault-tolerant (FT) spanner preserves approximate distances under network failures, often used in applications like network design and distributed systems. While classic (fault-free) spanners are believed to be easily extended to hypergraphs such as by the method of associated graphs, we reveal that this is not the case in the fault-tolerant setting: simple methods can only get a linear size in the maximum number of faults $f$. In contrast, all known optimal size of FT spanners are sublinear in $f$. Inspired by the FT clustering technique, we propose a clustering based algorithm that achieves an improved sublinear size bound. For an $n$-node $m$-edge hypergraph with rank $r$ and a sketch parameter $k$, our algorithm constructs edge FT (EFT) hyperspanners of stretch $2k-1$ and size $O(k^2f^{1-1/(rk)}n^{1+1/k}\log n)$ with high probability in time $\widetilde{O}(mr^3+fn)$. We also establish a lower bound of $Ω(f^{1-1/r-1/rk}n^{1+1/k-o(1)})$ edges for EFT hyperspanners, which leaves a gap of poly$(k)f^{1/r}$. Finally, we provide an algorithm for constructing additive EFT hyperspanners by combining multiplicative EFT hyperspanners with additive hyperspanners. We believe that our work will spark interest in developing optimal FT spanners for hypergraphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。