Abstract
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges F⊆G, the faulty-degree °(F) is the largest number of faults in F incident to any given vertex. We design new fault-tolerant structures with size comparable to previous constructions, but which tolerate every fault set of small faulty-degree °(F), rather than only fault sets of small size |F|. Our main results are:
- New FT-Certificates: For every n-vertex graph G and degree threshold f, one can compute a connectivity certificate H⊆G with |E(H)|=O˜(fn) edges that has the following guarantee: for any edge set F with faulty-degree °(F)≤f and every vertex pair u,v, it holds that u and v are connected in H∖F iff they are connected in G∖F. This bound on |E(H)| is nearly tight. Since our certificates handle some fault sets of size up to |F|=O(fn), prior work did not imply any nontrivial upper bound for this problem, even when f=1.
- New FT-Spanners: We show that every n-vertex graph G admits a (2k−1)-spanner H with |E(H)|=Ok(f1−1/kn1+1/k) edges, which tolerates any fault set F of faulty-degree at most f. This bound on |E(H)| optimal up to its hidden dependence on k, and it is close to the bound of Ok(|F|1/2n1+1/k+|F|n) that is known for the case where the total number of faults is |F| [Bodwin, Dinitz, Robelle SODA '22]. Our proof of this theorem is non-constructive, but by following a proof strategy of Dinitz and Robelle [PODC '20], we show that the runtime can be made polynomial by paying an additional polylog n factor in spanner size.
- New FT-Certificates: For every n-vertex graph G and degree threshold f, one can compute a connectivity certificate H⊆G with |E(H)|=O˜(fn) edges that has the following guarantee: for any edge set F with faulty-degree °(F)≤f and every vertex pair u,v, it holds that u and v are connected in H∖F iff they are connected in G∖F. This bound on |E(H)| is nearly tight. Since our certificates handle some fault sets of size up to |F|=O(fn), prior work did not imply any nontrivial upper bound for this problem, even when f=1.
- New FT-Spanners: We show that every n-vertex graph G admits a (2k−1)-spanner H with |E(H)|=Ok(f1−1/kn1+1/k) edges, which tolerates any fault set F of faulty-degree at most f. This bound on |E(H)| optimal up to its hidden dependence on k, and it is close to the bound of Ok(|F|1/2n1+1/k+|F|n) that is known for the case where the total number of faults is |F| [Bodwin, Dinitz, Robelle SODA '22]. Our proof of this theorem is non-constructive, but by following a proof strategy of Dinitz and Robelle [PODC '20], we show that the runtime can be made polynomial by paying an additional polylog n factor in spanner size.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Editors | David P Woodruff |
Pages | 2609-2642 |
Number of pages | 34 |
ISBN (Electronic) | 978-1-61197-791-2 |
DOIs | |
Publication status | Published Online - 4 Jan 2024 |
Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |
Conference
Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Country/Territory | United States |
City | Alexandria |
Period | 7/1/24 → 10/1/24 |
Funding
[email protected]. Supported by NSF:AF 2153680. [email protected]. Supported by the European Research Council (ERC grant 949272). [email protected]. Supported by the European Research Council (ERC grant 949083) and the Israeli Science Foundation (ISF), grant 2084/18