View PDF HTML (experimental)

Abstract:In this paper, we initiate the study on fault-tolerant (FT) graph spanners for hypergraphs and show the generalization to hypergraphs in the FT setting is non-trivial. An FT spanner approximates shortest distances under network failures, widely used in applications such as routing and distributed computing. We first provide a systematic study on extending spanners to hyperspanners in both non-faulty and FT settings and reveal that the latter case is more interesting: simple methods can only produce a linear size in the number of allowed faults $f$, while all known optimal sizes of FT graph spanners are sublinear in $f$. Inspired by the FT clustering technique in Parter's paper \cite{partervft}, we propose a hypergraph clustering based algorithm with an improved sublinear size bound. Specifically, for an $n$-node $m$-edge hypergraph with rank $r$ and a stretch parameter $k$, our algorithm constructs edge FT (EFT) hyperspanners of stretch $2k-1$ and size $O(k(k+r)f^{1-1/(rk)}n^{1+1/k}\log n)$ with high probability in time $\widetilde{O}(mr^3+nrf)$ ($\widetilde{O}$ hides polylogarithmic factors). We also establish size lower bounds, $\Omega((f/r)^{r-1-1/k+o(1)}n^{1+1/k-o(1)})$ for vertex FT (VFT) hyperspanners and $\Omega(f^{1-1/r-1/(rk)+o(1)}n^{1+1/k-o(1)}+fn)$ for EFT hyperspanners, leaving a gap of $k(k+r)f^{1/r}$ yet to close. We believe that this work will spark interest in developing optimal-sized FT hyperspanners for hypergraphs.

Submission history

From: Chunjiang Zhu [view email]
[v1] Thu, 27 Nov 2025 23:23:19 UTC (41 KB)
[v2] Mon, 9 Mar 2026 02:11:17 UTC (75 KB)
[v3] Sun, 30 Aug 2026 17:04:03 UTC (60 KB)