An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model

Authors Surender Baswana, Keerti Choudhary, Liam Roditty



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.72.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Surender Baswana
Keerti Choudhary
Liam Roditty

Cite As Get BibTex

Surender Baswana, Keerti Choudhary, and Liam Roditty. An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.72

Abstract

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph G=(V,E) with n=|V| and m=|E|, and an integer value k\geq 1, there is an algorithm that computes in O(2^{k}n log^2 n) time for any set F of size at most k  the strongly connected components of the graph G\F. The running time of our algorithm is almost optimal since the time for outputting the SCCs of G\F is at least \Omega(n). The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size O(2^{k} n^2).

Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically  rather than linearly  in  the  size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.

Subject Classification

Keywords
  • Fault tolerant
  • Directed graph
  • Strongly connected components

Metrics

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

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.53,
  2. 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, Cambridge, MA, USA, June 18-21, 2016, pages 509-518, 2016. URL: http://dx.doi.org/10.1145/2897518.2897648.
  3. Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In STOC'09: Proceedings of the 41st annual ACM symposium on Theory of computing, pages 101-110, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/http://doi.acm.org/10.1145/1536414.1536431.
  4. 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
  5. Shiri Chechik. Fault-tolerant compact routing schemes for general graphs. Inf. Comput., 222:36-44, 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.10.009,
  6. Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + epsilon)-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. URL: http://dx.doi.org/10.1137/1.9781611974782.96,
  7. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis. Decremental single-source reachability and strongly connected components in O(m√n) total update time. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 315-324, 2016. Google Scholar
  8. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Algorithmica, 63(4):861-882, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9543-0,
  9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  10. 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. URL: http://dx.doi.org/http://dx.doi.org/10.1137/S0097539705429847.
  11. 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. URL: http://doi.acm.org/10.1145/1993806.1993830, URL: http://dx.doi.org/10.1145/1993806.1993830.
  12. 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
  13. 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. URL: http://doi.acm.org/10.1145/1806689.1806754, URL: http://dx.doi.org/10.1145/1806689.1806754.
  14. 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
  15. Daniele Frigioni, Tobias Miller, Umberto Nanni, and Christos D. Zaroliagis. An experimental study of dynamic algorithms for transitive closure. ACM Journal of Experimental Algorithmics, 6:9, 2001. URL: http://doi.acm.org/10.1145/945394.945403, URL: http://dx.doi.org/10.1145/945394.945403.
  16. Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. Strong connectivity in directed graphs under failures, with applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1880-1899, 2017. Google Scholar
  17. 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, New Brunswick, NJ, USA, October 20-23, 2012, pages 748-757, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.17,
  18. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 674-683, 2014. URL: http://doi.acm.org/10.1145/2591796.2591869, URL: http://dx.doi.org/10.1145/2591796.2591869.
  19. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21-30, 2015. URL: http://doi.acm.org/10.1145/2746539.2746609, URL: http://dx.doi.org/10.1145/2746539.2746609.
  20. Giuseppe F. Italiano. Finding paths and deleting edges in directed acyclic graphs. Inf. Process. Lett., 28(1):5-11, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90136-6,
  21. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131-1142, 2013. Google Scholar
  22. Neelesh Khanna and Surender Baswana. Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graphs. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 513-524, 2010. Google Scholar
  23. Jakub Lacki. Improved deterministic algorithms for decremental transitive closure and strongly connected components. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1438-1445, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.111.
  24. 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. URL: http://dx.doi.org/10.1145/2767386.2767408.
  25. 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
  26. 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. URL: http://dx.doi.org/10.1109/FOCS.2007.54.
  27. Liam Roditty. Decremental maintenance of strongly connected components. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1143-1150, 2013. Google Scholar
  28. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput., 37(5):1455-1471, 2008. Google Scholar
  29. Daniel D. Sleator and Robert E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26:362-391, 1983. Google Scholar
  30. Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
  31. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms, 9(2):14, 2013. URL: http://dx.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