Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Sparse Weight Tolerant Subgraph for Single Source Shortest Path

Authors Diptarka Chakraborty, Debarati Das

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.15.pdf
  • Filesize: 401 kB
  • 15 pages

Document Identifiers

Author Details

Diptarka Chakraborty
  • Computer Science Institute of Charles University, Prague, Czech Republic
Debarati Das
  • Computer Science Institute of Charles University, Prague, Czech Republic

Funding

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 616787.

Cite AsGet BibTex

Diptarka Chakraborty and Debarati Das. Sparse Weight Tolerant Subgraph for Single Source Shortest Path. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.15

Abstract

In this paper we address the problem of computing a sparse subgraph of any weighted directed graph such that the exact distances from a designated source vertex to all other vertices are preserved under bounded weight increment. Finding a small sized subgraph that preserves distances between any pair of vertices is a well studied problem. Since in the real world any network is prone to failures, it is natural to study the fault tolerant version of the above problem. Unfortunately, it turns out that there may not always exist such a sparse subgraph even under single edge failure [Demetrescu et al. '08]. However in real applications it is not always the case that a link (edge) in a network becomes completely faulty. Instead, it can happen that some links become more congested which can be captured by increasing weight on the corresponding edges. Thus it makes sense to try to construct a sparse distance preserving subgraph under the above weight increment model where total increase in weight in the whole network (graph) is bounded by some parameter k. To the best of our knowledge this problem has not been studied so far. In this paper we show that given any weighted directed graph with n vertices and a source vertex, one can construct a subgraph of size at most e * (k-1)!2^kn such that it preserves distances between the source and all other vertices as long as the total weight increment is bounded by k and we are allowed to only have integer valued (can be negative) weight on edges and also weight of an edge can only be increased by some positive integer. Next we show a lower bound of c * 2^kn, for some constant c >= 5/4, on the size of such a subgraph. We further argue that the restrictions of integral weight and integral weight increment are actually essential by showing that if we remove any one of these two we may need to store Omega(n^2) edges to preserve the distances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Shortest path
  • fault tolerant
  • distance preserver
  • graph algorithm

Metrics

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

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 351-361, 2016. Google Scholar
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 568-576, 2017. 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, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 672-681, 2005. Google Scholar
  6. Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 101-110, 2009. Google Scholar
  7. 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
  8. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees. In Algorithms - ESA 2014 - 22th Annual European Symposium, Proceedings, pages 137-148, 2014. Google Scholar
  9. 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
  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. Gilad Braunschvig, Shiri Chechik, David Peleg, and Adam Sealfon. Fault tolerant additive and (μ, α)-spanners. Theor. Comput. Sci., 580:94-100, 2015. Google Scholar
  12. Luciana S. Buriol, Mauricio G. C. Resende, and Mikkel Thorup. Speeding up dynamic shortest-path algorithms. INFORMS Journal on Computing, 20(2):191-204, 2008. Google Scholar
  13. Diptarka Chakraborty and Debarati Das. Near optimal sized weight tolerant subgraph for single source shortest path. CoRR, abs/1707.04867, 2017. Google Scholar
  14. 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
  15. 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
  16. Artur Czumaj and Hairong Zhao. Fault-tolerant geometric spanners. Discrete & Computational Geometry, 32(2):207-230, 2004. Google Scholar
  17. Camil Demetrescu and Giuseppe F. Italiano. Fully dynamic all pairs shortest paths with real edge weights. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pages 260-267, 2001. Google Scholar
  18. 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
  19. 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
  20. 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
  21. D. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 2010. Google Scholar
  22. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 748-757, 2012. Google Scholar
  23. 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
  24. 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
  25. 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
  26. Merav Parter. Vertex fault tolerant additive spanners. In Distributed Computing - 28th International Symposium, DISC 2014, Proceedings, pages 167-181, 2014. Google Scholar
  27. 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
  28. 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
  29. 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
  30. G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest path problem. Journal of Algorithms, 21:267-305, 1996. Google Scholar
  31. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms, 8(4):33:1-33:11, 2012. Google Scholar
  32. Hans Rohnert. A dynamization of the all pairs least cost path problem. In STACS 85, 2nd Symposium of Theoretical Aspects of Computer Science, Proceedings, pages 279-286, 1985. Google Scholar
  33. Mohammadreza Saeedmanesh and Nikolas Geroliminis. Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks. Transportation Research Part B: Methodological, 105(Supplement C):193-211, 2017. Google Scholar
  34. 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), pages 406-411, 2005. Google Scholar
  35. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms, 9(2):14:1-14:13, 2013. Google Scholar
  36. Virginia Vassilevska Williams. Faster replacement paths. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 1337-1346, 2011. Google Scholar
  37. David P. Woodruff. Additive spanners in nearly quadratic time. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, pages 463-474, 2010. 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 Imprint Privacy Contact