Document Open Access Logo

Pairwise Reachability Oracles and Preservers Under Failures

Authors Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.35.pdf
  • Filesize: 0.89 MB
  • 16 pages

Document Identifiers

Author Details

Diptarka Chakraborty
  • National University of Singapore, Singapore
Kushagra Chatterjee
  • National University of Singapore, Singapore
Keerti Choudhary
  • Indian Institute of Technology Delhi, India

Funding

  • Chakraborty, Diptarka: The author is supported in part by NUS ODPRT Grant, WBS No. A-0008078-00-00.
  • Chatterjee, Kushagra: The author is supported in part by NUS ODPRT Grant, WBS No. A-0008078-00-00.
  • Choudhary, Keerti: The author is supported in part by Google India Algorithms Research grant 2021.

Acknowledgements

The authors would like to thank anonymous reviewers for many helpful comments on a preliminary version of this work, especially for pointing out [Bodwin, 2020].

Cite As Get BibTex

Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary. Pairwise Reachability Oracles and Preservers Under Failures. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.35

Abstract

In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let G = (V, E) be a directed graph on n-nodes, and P ⊆ V× V be a set of vertex pairs in G. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we provide extremal bounds for sparse fault-tolerant reachability preservers, resilient to two or more failures. Prior to this work, such oracles and reachability preservers were widely studied for the special scenario of single-source and all-pairs settings. However, for the scenario of arbitrary pairs, no prior (non-trivial) results were known for dual (or more) failures, except those implied from the single-source setting. One of the main questions is whether it is possible to beat the O(n |P|) size bound (derived from the single-source setting) for reachability oracle and preserver for dual failures (or O(2^k n|P|) bound for k failures). We answer this question affirmatively. Below we summarize our contributions.
- For an n-vertex directed graph G = (V, E) and P ⊆ V× V, we present a construction of O(n √{|P|}) sized dual fault-tolerant pairwise reachability oracle with constant query time. We further provide a matching (up to the word size) lower bound of Ω(n √{|P|}) on the size (in bits) of the oracle for the dual fault setting, thereby proving that our oracle is (near-)optimal.
- Next, we provide a construction of O(n + min{|P|√ n,~n√{|P|}}) sized oracle with O(1) query time, resilient to single node/edge failure. In particular, for |P| bounded by O(√n) this yields an oracle of just O(n) size. We complement the upper bound with a lower bound of Ω(n^{2/3}|P|^{1/2}) (in bits), refuting the possibility of a linear-sized oracle for P of size ω(n^{2/3}).
- We also present a construction of O(n^{4/3} |P|^{1/3}) sized pairwise reachability preservers resilient to dual edge/vertex failures. Previously, such preservers were known to exist only under single failure and had O(n+min{|P|√n,~n√ {|P|}}) size [Chakraborty and Choudhary, ICALP'20]. We also show a lower bound of Ω(n √{|P|}) edges on the size of dual fault-tolerant reachability preservers, thereby providing a sharp gap between single and dual fault-tolerant reachability preservers for |P| = o(n). 
- Finally, we provide a generic pairwise reachability preserver construction that provides a o(2^k n |P|) sized subgraph resilient to k failures, for any k ≥ 1. Before this work, we only knew of an O(2^k n |P|) bound implied from the single-source setting [Baswana, Choudhary, and Roditty, STOC'16].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Sparsification and spanners
Keywords
  • Fault-tolerant
  • Reachability Oracle
  • Reachability Preservers
  • Graph sparsification
  • Lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud and Greg Bodwin. Reachability preservers: New extremal bounds and approximation algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1865-1883, 2018. Google Scholar
  2. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS in undirected graphs: Breaking the o(m) barrier. SIAM J. Comput., 48(4):1335-1363, 2019. Google Scholar
  3. Surender Baswana, Keerti Choudhary, Moazzam Hussain, and Liam Roditty. Approximate single source fault tolerant shortest path. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1901-1915, 2018. Google Scholar
  4. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: generic and optimal. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 509-518, 2016. Google Scholar
  5. Surender Baswana and Neelesh Khanna. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica, 66(1):18-50, 2013. Google Scholar
  6. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Proceedings, pages 167-178, 2015. Google Scholar
  7. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-edge-fault-tolerant approximate shortest-path trees. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pages 18:1-18:14, 2016. Google Scholar
  8. Greg Bodwin. Linear size distance preservers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 600-615, 2017. Google Scholar
  9. Greg Bodwin. A note on distance-preserving graph sparsification. arXiv preprint arXiv:2001.07741, 2020. Google Scholar
  10. Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 73:1-73:14, 2017. Google Scholar
  11. Diptarka Chakraborty and Keerti Choudhary. New extremal bounds for reachability and strong-connectivity preservers under failures. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 25:1-25:20, 2020. Google Scholar
  12. Diptarka Chakraborty and Debarati Das. Sparse Weight Tolerant Subgraph for Single Source Shortest Path. In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  13. T-H Hubert Chan, Michael Dinitz, and Anupam Gupta. Spanners with slack. In European Symposium on Algorithms, pages 196-207. Springer, 2006. Google Scholar
  14. Shiri Chechik. Fault-tolerant compact routing schemes for general graphs. Inf. Comput., 222:36-44, 2013. Google Scholar
  15. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault-tolerant spanners for general graphs. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 435-444, 2009. Google Scholar
  16. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. In 18th Annual European Symposium on Algorithms - ESA (1), pages 84-96, 2010. Google Scholar
  17. Keerti Choudhary. An optimal dual fault tolerant reachability oracle. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 130:1-130:13, 2016. Google Scholar
  18. Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math., 20(2):463-501, 2006. Google Scholar
  19. Artur Czumaj and Hairong Zhao. Fault-tolerant geometric spanners. Discrete & Computational Geometry, 32(2):207-230, 2004. Google Scholar
  20. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37(5):1299-1318, 2008. Google Scholar
  21. Michael Dinitz. Compact routing with slack. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 81-88, 2007. Google Scholar
  22. 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, pages 169-178, 2011. Google Scholar
  23. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pages 506-515, 2009. Google Scholar
  24. Ran Duan and Seth Pettie. Connectivity oracles for failure prone graphs. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 465-474, 2010. Google Scholar
  25. Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 490-509, 2017. Google Scholar
  26. Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 127:1-127:15, 2017. Google Scholar
  27. Goran Konjevod, Andrea Werneck Richa, Donglin Xia, and Hai Yu. Compact routing with slack in low doubling dimension. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 71-80, 2007. Google Scholar
  28. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Comput. Complex., 8(1):21-49, 1999. Google Scholar
  29. Thomas Lengauer and Robert Endre Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst., 1(1):121-141, 1979. Google Scholar
  30. Tamás Lukovszki. New results of fault tolerant geometric spanners. In Algorithms and Data Structures, 6th International Workshop, WADS '99, Proceedings, pages 193-204, 1999. Google Scholar
  31. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  32. Merav Parter. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 481-490, 2015. Google Scholar
  33. Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In Algorithms - ESA 2013 - 21st Annual European Symposium, Proceedings, pages 779-790, 2013. Google Scholar
  34. Merav Parter and David Peleg. Fault tolerant approximate BFS structures. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 1073-1092, 2014. Google Scholar
  35. Mihai Patrascu and Mikkel Thorup. Planning for fast connectivity updates. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 263-271, 2007. Google Scholar
  36. Robert Endre Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6:171-185, 1976. URL: https://doi.org/10.1007/BF00268499.
  37. Jan van den Brand and Thatchaphol Saranurak. Sensitive distance and reachability oracles for large batch updates. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 424-435, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact