Document Open Access Logo

An Optimal Dual Fault Tolerant Reachability Oracle

Author Keerti Choudhary

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.130.pdf
  • Filesize: 0.8 MB
  • 13 pages

Document Identifiers

Author Details

Keerti Choudhary

Cite As Get BibTex

Keerti Choudhary. An Optimal Dual Fault Tolerant Reachability Oracle. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 130:1-130:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.130

Abstract

Let G=(V,E) be an n-vertices m-edges directed graph. Let s inV be any designated source vertex. We address the problem of reporting the reachability information from s under two vertex failures. We show that it is possible to compute in polynomial time an O(n) size data structure that for any query vertex v, and any pair of failed vertices f_1, f_2, answers in O(1) time whether or not there exists a path from s to v in G\{f_1,f_2}.

For the simpler case of single vertex failure such a data structure can be obtained using the dominator-tree from the celebrated work of Lengauer and Tarjan [TOPLAS 1979, Vol. 1]. However, no efficient data structure was known in the past for handling more than one failures. We, in addition, also present a labeling scheme with O(log^3(n))-bit size labels such that for any f_1, f_2, v in V , it is possible to determine in poly-logarithmic time if v is reachable from s in G\{f_1,f_2} using only the labels of f1, f_2 and v.

Our data structure can also be seen as an efficient mechanism for verifying double-dominators. For any given x, y, v in V we can determine in O(1) time if the pair (x,y) is a double-dominator of v. Earlier the best known method for this problem was using dominator chain from which verification of double-dominators of only a single vertex was possible.

Subject Classification

Keywords
  • Fault tolerant
  • Directed graph
  • Reachability oracle
  • Labeling scheme

Metrics

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

References

  1. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: Generic and optimal. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 19-21, 2016 (to appear), 2016. Google Scholar
  2. 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
  3. Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, and Jeffery Westbrook. Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput., 38(4):1533-1573, 2008. Google Scholar
  4. Shiri Chechik. Fault-tolerant compact routing schemes for general graphs. Inf. Comput., 222:36-44, 2013. Google Scholar
  5. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Algorithmica, 63(4):861-882, 2012. Google Scholar
  6. Erik D. Demaine, Gad M. Landau, and Oren Weimann. On cartesian trees and range minimum queries. Algorithmica, 68(3):610-625, 2014. Google Scholar
  7. 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
  8. 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. Google Scholar
  9. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In SODA'09: Proceedings of 19th Annual ACM - SIAM Symposium on Discrete Algorithms, pages 506-515, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. Google Scholar
  10. Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, and Robert Endre Tarjan. Finding dominators via disjoint set union. J. Discrete Algorithms, 23:2-20, 2013. Google Scholar
  11. Loukas Georgiadis and Robert Endre Tarjan. Dominators, directed bipolar orders, and independent spanning trees. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 375-386, 2012. Google Scholar
  12. 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
  13. Merav Parter. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 481-490, 2015. Google Scholar
  14. Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 779-790, 2013. Google Scholar
  15. 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, Portland, Oregon, USA, January 5-7, 2014, pages 1073-1092, 2014. Google Scholar
  16. Maxim Teslenko and Elena Dubrova. An efficient algorithm for finding double-vertex dominators in circuit graphs. In 2005 Design, Automation and Test in Europe Conference and Exposition (DATE 2005), 7-11 March 2005, Munich, Germany, pages 406-411, 2005. Google Scholar
  17. Virginia Vassilevska Williams. Faster replacement paths. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1337-1346, 2011. 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