Deterministic Replacement Path Covering
Article No.: 34, Pages 1 - 35
Abstract
In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph \(G\), a vertex pair \((s,t)\in V(G)\times V(G)\), and a set of edge faults \(F\subseteq E(G)\), a replacement path \(P(s,t,F)\) is an \(s\)-\(t\) shortest path in \(G\setminus F\). For integer parameters \(L,f\), a replacement path covering (\(\mathsf{RPC}\)) is a collection of subgraphs of \(G\), denoted by \(\mathcal{G}_{L,f}=\{G_{1},\ldots,G_{r}\}\), such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\)) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\). The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\).
In the randomized setting, it is easy to build an \((L,f)\)-\(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\), but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following:
—
There exist efficient deterministic constructions of \((L,f)\)-\(\mathsf{RPC}\)s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes.
—
For every \(L,f\), and \(n\), there exists an \(n\)-vertex graph \(G\) whose \((L,f)\)-\(\mathsf{RPC}\) covering value is \(\Omega(L^{f})\). This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures.
An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts.
References
[1]
Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, and Endre Szemerédi. 1992. Fault tolerant graphs, perfect hash functions and disjoint paths. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. 693–702. DOI:
[2]
Noga Alon. 1986. Explicit construction of exponential sized families of k-independent sets. Discrete Mathematics 58, 2 (1986), 191–193. DOI:
[3]
Noga Alon, Shiri Chechik, and Sarel Cohen. 2019. Deterministic combinatorial replacement paths and distance sensitivity oracles. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19). 12:1–12:14.
[4]
Noga Alon and Shai Gutner. 2010. Balanced families of perfect hash functions and their applications. ACM Transactions on Algorithms 6, 3 (2010), 54:1–54:12. DOI:
[5]
Noga Alon, Dana Moshkovitz, and Shmuel Safra. 2006. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms 2, 2 (2006), 153–177. DOI:
[6]
Noga Alon and Moni Naor. 1996. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 4–5 (1996), 434–449.
[7]
Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. Journal of the ACM (JACM) 42, 4 (1995), 844–856.
[8]
Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. 2018. Optimal vertex fault tolerant spanners (for fixed stretch). In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1884–1900.
[9]
Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2020. Optimal vertex fault-tolerant spanners in polynomial time. DOI: https://dl.acm.org/doi/10.14778/3551793.3551794
[10]
Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon. 2015. Fault tolerant additive and (\(\mu\), \(\alpha\))-spanners. Theoretical Computer Science 580 (2015), 94–100.
[11]
Diptarka Chakraborty and Keerti Choudhary. 2020. New extremal bounds for reachability and strong-connectivity preservers under failures. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP ’20). 25:1–25:20.
[12]
Shiri Chechik and Sarel Cohen. 2020. Distance sensitivity oracles with subcubic preprocessing time and fast query time. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20). 1375–1388.
[13]
Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 2017. (1+∊)-approximate f-sensitive distance oracles. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1479–1496.
[14]
Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2010. Fault tolerant spanners for general graphs. SIAM Journal on Computing 39, 7 (2010), 3403–3423.
[15]
Julia Chuzhoy, Merav Parter, and Zihan Tan. 2020. On packing low-diameter spanning trees. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP ’20). 33:1–33:18.
[16]
Michael Dinitz and Robert Krauthgamer. 2011. Fault-tolerant spanners: Better and simpler. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. ACM, New York, NY, 169–178.
[17]
Michael Dinitz and Caleb Robelle. 2020b. Efficient and simple algorithms for fault-tolerant spanners. In PODC ’20: ACM Symposium on Principles of Distributed Computing. 493–500.
[18]
Emanuela Fachini and Alon Nilli. 2001. Recursive bounds for perfect hashing. Discrete Applied Mathematics 111, 3 (2001), 307–311. DOI:
[19]
Michael L. Fredman and János Komlós. 1984. On the size of separating systems and families of perfect hash functions. SIAM Journal on Algebraic and Discrete Methods 5, 1 (1984), 61–68. DOI:
[20]
Michael L. Fredman, János Komlós, and Endre Szemerédi. 1984. Storing a sparse table with 0(1) worst case access time. Journal of the ACM 31, 3 (1984), 538–544. DOI:
[21]
Arnaldo Garcia and Henning Stichtenoth. 1996. On the asymptotic behaviour of some towers of function fields over finite fields. Journal of Number Theory 61, 2 (1996), 248–273. DOI:
[22]
Valerii Denisovich Goppa. 1970. A new class of linear correcting codes. Problemy Peredachi Informatsii 6, 3 (1970), 24–30.
[23]
Fabrizio Grandoni and Virginia Vassilevska Williams. 2020. Faster replacement paths and distance sensitivity oracles. ACM Transactions on Algorithms 16, 1 (2020), 15:1–15:25. DOI:
[24]
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. 2019. Essential Coding Theory. Retrieved from http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/book.
[25]
Yael Hitron and Merav Parter. 2020. Round-efficient distributed byzantine computation. DOI:
[26]
Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. 182–191. DOI:
[27]
Alon Nilli. 1994. Perfect hashing and probability. Combinatorics, Probability and Computing 3 (1994), 407–409. DOI:
[28]
Merav Parter. 2015. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. 481–490.
[29]
Merav Parter. 2019a. Small cuts and connectivity certificates: A fault tolerant approach. In Proceedings of the 33rd International Symposium on Distributed Computing.
[30]
Merav Parter. 2019b. Small cuts and connectivity certificates: A fault tolerant approach. Retrieved from https://arxiv.org/abs/1908.03022
[31]
Merav Parter. 2022. Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel. In Proceedings of the STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing. Stefano Leonardi and Anupam Gupta (Eds.). ACM, New York, NY, 1080–1092. DOI:
[32]
Merav Parter and David Peleg. 2016. Sparse fault-tolerant BFS structures. ACM Transactions on Algorithms 13, 1 (2016), 11:1–11:24.
[33]
Merav Parter and Eylon Yogev. 2019a. Low congestion cycle covers and their applications. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’19). 1673–1692.
[34]
Merav Parter and Eylon Yogev. 2019b. Secure distributed computing made (nearly) optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC ’19). 107–116. DOI:
[35]
Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics (SIAM) 8, 2 (1960), 300–304.
[36]
Jeanette P. Schmidt and Alan Siegel. 1990. The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing 19, 5 (1990), 775–786. DOI:
[37]
Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar. 2001. A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound. IEEE Transactions on Information Theory 47, 6 (2001), 2225–2241. DOI:
[38]
Richard C. Singleton. 1964. Maximum distance q -nary codes. IEEE Transactions on Information Theory 10, 2 (1964), 116–118. https://doi.org/10.1109/TIT.1964.1053661
[39]
M. A. Tsfasman, S. G. Vlădutx, and Th. Zink. 1982. Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Mathematische Nachrichten 109, 1 (1982), 21–28. DOI:
[40]
Jan van den Brand and Thatchaphol Saranurak. 2019. Sensitive distance and reachability oracles for large batch updates. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS ’19). IEEE, 424–435.
[41]
Huaxiong Wang and Chaoping Xing. 2001. Explicit constructions of perfect hash families from algebraic curves over finite fields. Journal of Combinatorial Theory, Series A 93, 1 (2001), 112–124. DOI:
[42]
Oren Weimann and Raphael Yuster. 2013. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms (TALG) 9, 2 (2013), 14.
[43]
Raphael Yuster and Uri Zwick. 2005. Answering distance queries in directed graphs using fast matrix multiplication. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’05). IEEE, 389–396.
Index Terms
- Deterministic Replacement Path Covering
Recommendations
Deterministic replacement path covering
SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete AlgorithmsIn this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph G, a vertex pair (s, t) ∈ V(G) × V(G), and a set of edge faults F ⊆ E(G), a replacement path P(s, ...
Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and ArchitecturesWe consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as measured by the standard notion of arboricity. For the problems of maximal ...
Optimal deterministic approximate parallel prefix sums and their applications
ISTCS '95: Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95)Abstract: We show that extremely accurate approximation to the prefix sums of a sequence of n integers can be computed deterministically in O(log log n) time using O(n/log log n) processors in the COMMON CRCW PRAM model. This complements randomized ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 August 2024
Online AM: 18 June 2024
Accepted: 12 June 2024
Revised: 25 April 2024
Received: 29 May 2023
Published in TALG Volume 20, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Sponsor Israel Science Foundation
- Sponsor Len Blavatnik and the Blavatnik Family foundation, and the Sponsor Simons Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 73Total Downloads
- Downloads (Last 12 months)73
- Downloads (Last 6 weeks)6
Reflects downloads up to 05 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in