Sublinear Edge Fault Tolerant Spanners for Hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915844670357504 |
|---|---|
| author | He, Jialin Popescu, Nicholas Zhu, Chunjiang |
| author_facet | He, Jialin Popescu, Nicholas Zhu, Chunjiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22803 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sublinear Edge Fault Tolerant Spanners for Hypergraphs He, Jialin Popescu, Nicholas Zhu, Chunjiang Data Structures and Algorithms 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. |
| title | Sublinear Edge Fault Tolerant Spanners for Hypergraphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.22803 |