Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
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_ | 1866911028119339008 |
|---|---|
| author | Bhanja, Koustav Petruschka, Asaf |
| author_facet | Bhanja, Koustav Petruschka, Asaf |
| contents | We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any $f$ (or less) vertex failures occur. An $f$-FT Steiner connectivity labeling scheme for an $n$-vertex graph $G=(V,E)$ with terminal set $U \subseteq V$ provides labels to the vertices of $G$, such that given only the labels of any subset $F \subseteq V$ with $|F| \leq f$, one can determine if $U$ remains connected in $G-F$. The main complexity measure is the maximum label length.
The special case $U=V$ of global connectivity has been recently studied by Jiang, Parter, and Petruschka, who provided labels of $n^{1-1/f} \cdot \mathrm{poly}(f,\log n)$ bits. This is near-optimal (up to $\mathrm{poly}(f,\log n)$ factors) by a lower bound of Long, Pettie and Saranurak. Our scheme achieves labels of $|U|^{1-1/f} \cdot \mathrm{poly}(f, \log n)$ for general $U \subseteq V$, which is near-optimal for any given size $|U|$ of the terminal set. To handle terminal sets, our approach differs from Jiang et al. We use a well-structured Steiner tree for $U$ produced by a decomposition theorem of Duan and Pettie, and bypass the need for Nagamochi-Ibaraki sparsification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23215 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity Bhanja, Koustav Petruschka, Asaf Data Structures and Algorithms We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any $f$ (or less) vertex failures occur. An $f$-FT Steiner connectivity labeling scheme for an $n$-vertex graph $G=(V,E)$ with terminal set $U \subseteq V$ provides labels to the vertices of $G$, such that given only the labels of any subset $F \subseteq V$ with $|F| \leq f$, one can determine if $U$ remains connected in $G-F$. The main complexity measure is the maximum label length. The special case $U=V$ of global connectivity has been recently studied by Jiang, Parter, and Petruschka, who provided labels of $n^{1-1/f} \cdot \mathrm{poly}(f,\log n)$ bits. This is near-optimal (up to $\mathrm{poly}(f,\log n)$ factors) by a lower bound of Long, Pettie and Saranurak. Our scheme achieves labels of $|U|^{1-1/f} \cdot \mathrm{poly}(f, \log n)$ for general $U \subseteq V$, which is near-optimal for any given size $|U|$ of the terminal set. To handle terminal sets, our approach differs from Jiang et al. We use a well-structured Steiner tree for $U$ produced by a decomposition theorem of Duan and Pettie, and bypass the need for Nagamochi-Ibaraki sparsification. |
| title | Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.23215 |