Document Open Access Logo

Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem

Authors Dipan Dey, Manoj Gupta

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.42.pdf
  • Filesize: 0.8 MB
  • 18 pages

Document Identifiers

Author Details

Dipan Dey
  • IIT Gandhinagar, India
Manoj Gupta
  • IIT Gandhinagar, India

Cite AsGet BibTex

Dipan Dey and Manoj Gupta. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.42

Abstract

In a graph G with a source s, we design a distance oracle that can answer the following query: Query(s,t,e) - find the length of shortest path from a fixed source s to any destination vertex t while avoiding any edge e. We design a deterministic algorithm that builds such an oracle in Õ(m √n) time. Our oracle uses Õ(n √n) space and can answer queries in Õ(1) time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in Õ(m √n+n²) time. Using our distance oracle, we also solve the single source replacement path problem (Ssrp problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the Ssrp problem. The running time of their algorithm is Õ(m √n + n²). In this paper, we show that the Ssrp problem can be solved in Õ(m √n + |ℛ|) time, where ℛ is the output set of the Ssrp problem in G. Our Ssrp algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of Ω(m √n) for any combinatorial algorithm that solves this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Shortest paths
  • Theory of computation → Data structures design and analysis
Keywords
  • distance sensitivity oracle
  • single-source replacement paths

Metrics

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

Related Versions

References

  1. Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, pages 88-94, 2000. Google Scholar
  2. Aaron Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 742-755, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  3. Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 101-110. ACM, 2009. Google Scholar
  4. Aaron Bernstein and David R. Karger. Improved distance sensitivity oracles via random sampling. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 34-43. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347087.
  5. Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-optimal deterministic single-source distance sensitivity oracles. In Accepted in Annual European Symposium on Algorithms, ESA 2021, 2021. Google Scholar
  6. 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, February 17-20, 2016, Orléans, France, pages 18:1-18:14, 2016. Google Scholar
  7. 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, July 10-14, 2017, Warsaw, Poland, pages 73:1-73:14, 2017. Google Scholar
  8. Shiri Chechik and Sarel Cohen. Near optimal algorithms for the single source replacement paths problem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2090-2109, 2019. Google Scholar
  9. Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + ε)-approximate f-sensitive distance oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1479-1496, 2017. Google Scholar
  10. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM J. Comput., 39(7):3403-3423, 2010. URL: https://doi.org/10.1137/090758039.
  11. Shiri Chechik and Ofer Magen. Near optimal algorithm for the directed single source replacement paths problem. 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 81:1-81:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  12. 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
  13. Dipan Dey and Manoj Gupta. Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem. CoRR, abs/2206.15016, 2022. URL: https://doi.org/10.48550/arXiv.2206.15016.
  14. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 506-515, USA, 2009. Society for Industrial and Applied Mathematics. Google Scholar
  15. Ran Duan and Seth Pettie. Approximating maximum weight matching in near-linear time. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 673-682, Washington, DC, USA, 2010. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2010.70.
  16. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 748-757. IEEE, 2012. Google Scholar
  17. Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Trans. Algorithms, 16(1), December 2019. URL: https://doi.org/10.1145/3365835.
  18. Manoj Gupta, Rahul Jain, and Nitiksha Modi. Multiple source replacement path problem. In Yuval Emek and Christian Cachin, editors, PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 339-348. ACM, 2020. Google Scholar
  19. Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 127:1-127:15, 2017. Google Scholar
  20. Manoj Gupta and Aditi Singh. Generic single edge fault tolerant exact distance oracle. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 72:1-72:15, 2018. Google Scholar
  21. John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What is an edge worth? In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 252-259, 2001. Google Scholar
  22. Kavindra Malik, Ashok K Mittal, and Santosh K Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223-227, 1989. Google Scholar
  23. Enrico Nardelli, Guido Proietti, and Peter Widmayer. Finding the most vital node of a shortest path. Theor. Comput. Sci., 296(1):167-177, 2003. Google Scholar
  24. Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1-2):166-196, 2001. Google Scholar
  25. 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
  26. 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
  27. Liam Roditty. On the k shortest simple paths problem in weighted directed graphs. SIAM J. Comput., 39:2363-2376, January 2010. URL: https://doi.org/10.1137/080730950.
  28. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. In Proceedings of the 32nd International Conference on Automata, Languages and Programming, ICALP'05, pages 249-260, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11523468_21.
  29. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms, 9(2), March 2013. URL: https://doi.org/10.1145/2438645.2438646.
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 Imprint Privacy Contact