Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

Greg Bodwin, Bernhard Haeupler, Merav Parter

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
EditorsDavid P Woodruff
Pages2609-2642
Number of pages34
ISBN (Electronic)978-1-61197-791-2
DOIs
Publication statusPublished Online - 4 Jan 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: 7 Jan 202410 Jan 2024

Conference

Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States
CityAlexandria
Period7/1/2410/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

Fingerprint

Dive into the research topics of 'Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free'. Together they form a unique fingerprint.

Cite this