LIPIcs.ITCS.2023.20.pdf
- Filesize: 0.74 MB
- 22 pages
Document
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free
Authors
-
Part of:
Volume:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
Cite AsGet BibTex
Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.20
https://doi.org/10.4230/LIPIcs.ITCS.2023.20
Abstract
A t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior.
In particular, our main result is that, for (2k-1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n^{4/3}) edges that is robust to f = O(n^{2/9}) edge faults. It is well known that Ω(n^{4/3}) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k.
Subject Classification
ACM Subject Classification
- Theory of computation → Sparsification and spanners
Keywords
- Emulators
- Fault Tolerance
- Girth Conjecture
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence. Graph spanners: A tutorial review. Computer Science Review, 37:100253, 2020.
-
Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993.
- Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Epic fail: Emulators can tolerate polynomially many edge faults for free. CoRR, abs/2209.03675, 2022. URL: https://doi.org/10.48550/arXiv.2209.03675.
- Greg Bodwin, Michael Dinitz, and Yasamin Nazari. Vertex Fault-Tolerant Emulators. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1-25:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.25.
-
Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal vertex fault tolerant spanners (for fixed stretch). In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1884-1900. SIAM, 2018.
-
Greg Bodwin, Michael Dinitz, and Caleb Robelle. Optimal vertex fault-tolerant spanners in polynomial time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2021.
-
Greg Bodwin, Michael Dinitz, and Caleb Robelle. Partially optimal edge fault-tolerant spanners. In Proceedings of the Thirty-Thurd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, 2022.
- Greg Bodwin and Shyamal Patel. A trivial yet optimal solution to vertex fault tolerant spanners. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 541-543, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331588.
-
Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM J. Comput., 39(7):3403-3423, 2010.
-
Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 169-178, 2011.
-
Michael Dinitz and Caleb Robelle. Efficient and simple algorithms for fault-tolerant spanners. In Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing, PODC ’20, 2020.
-
Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000.
-
Paul Erdős. Extremal problems in graph theory. In In Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1964.
- Merav Parter. Nearly optimal vertex fault-tolerant spanners in optimal time: Sequential, distributed, and parallel. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1080-1092, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520047.
-
David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989.
-
David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740-747, 1989.