×

Strong connectivity in directed graphs under failures, with applications. (English) Zbl 1448.05116

This paper studies strong connectivity and components in directed graphs. Let \(G\) be a strongly connected graph and \(G^R\) be the reverse digraph of \(G\) and \(s\) be a vertex in \(G\). Denote by \(G_s\) the flow graph with start vertex \(s\) and \(G_s^R\) the reverse flow graph with start vertex \(s\). Given the two respective dominator trees \(D\) and \(D^R\), the loop nesting trees \(H\) and \(H^R\), and the strong bridges of \(G\), it is shown that we can compute the number of strongly connected components after the deletion of a strong bridge in \(O(n)\) time for all strong bridges. Algorithms are worked out to find all smallest and largest strongly connected components of \(G\backslash e\) for any edge \(e\). Moreover, if \(G\) has \(n\) vertices and \(m\) edges, it is shown that we can preprocess \(G\) in \(O(m)\) time and construct an \(O(n)\) space data structure so that we can determine in \(O(n)\) time all the strongly connected components of \(G\backslash u\) given a vertex \(u\). Algorithms with pseudocode are worked out. Furthermore, it is shown that we can compute in \(O(m+n)\) time a sparse certificate that maintains the same 1-connectivity cuts and decompositions induced by the 1-connectivity cuts together with the 2-edge and 2-vertex-connected components.

MSC:

05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling. Volume 2: Compiling, Prentice-Hall, Englewood Cliffs, NJ, 1972, https://dl.acm.org/doi/10.5555/578789.
[2] S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup, Dominators in linear time, SIAM J. Comput., 28 (1989), pp. 2117-2132, https://doi.org/10.1137/S0097539797317263. · Zbl 0939.68158
[3] A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos, Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36 (2009), pp. 2193-2200, https://doi.org/10.1016/j.cor.2008.08.016. · Zbl 1158.90411
[4] S. Baswana, K. Choudhary, and L. Roditty, An efficient strongly connected components algorithm in the fault tolerant model, Algorithmica, 81 (2019), pp. 967-985, https://doi.org/10.1007/s00453-018-0452-3. · Zbl 1418.68159
[5] A. A. Benczúr, Counterexamples for directed and node capacitated cut-trees, SIAM J. Comput., 24 (1995), pp. 505-510, https://doi.org/10.1137/S0097539792236730. · Zbl 0833.90038
[6] S. P. Borgatti, Identifying sets of key players in a social network, Comput. Math. Org. Theory, 12 (2006), pp. 21-34, https://doi.org/10.1007/s10588-006-7084-x. · Zbl 1198.91180
[7] A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook, Linear-time algorithms for dominators and other path-evaluation problems, SIAM J. Comput., 38 (2008), pp. 1533-1573, https://doi.org/10.1137/070693217. · Zbl 1181.05079
[8] M. Cairo, P. Medvedev, N. O. Acosta, , R. Rizzi, and A. I. Tomescu, An optimal \(o(nm)\) algorithm for enumerating all walks common to all closed edge-covering walks of a graph, ACM Trans. Algorithms, 15 (2019), https://doi.org/10.1145/3341731. · Zbl 1454.92021
[9] M. Cairo, R. Rizzi, A. I. Tomescu, and E. C. Zirondelli, From Omnitigs to Macrotigs: A Linear-Time Algorithm for Safe Walks-Common to all Closed Arc-Coverings of a Directed Graph, https://arxiv.org/abs/2002.10498, 2020.
[10] S. Chechik, T. D. Hansen, G. F. Italiano, V. Loitzenbauer, and N. Parotsidis, Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, https://doi.org/10.1137/1.9781611974782.12. · Zbl 1410.05196
[11] R. Cohen, S. Havlin, and D. ben-Avraham, Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett., 91 (2003), 247901, https://doi.org/10.1103/PhysRevLett.91.247901.
[12] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Trans. Program. Languages Systems, 13 (1991), pp. 451-490, https://doi.org/10.1145/115372.115320.
[13] C. Demetrescu, M. Thorup, R. A. Chowdhury, and V. Ramachandran, Oracles for distances avoiding a failed node or link, SIAM J. Comput., 37 (2008), pp. 1299-1318, https://doi.org/10.1137/S0097539705429847. · Zbl 1158.05057
[14] W. Di Luigi, L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis, 2-connectivity in directed graphs: An experimental study, in Proceedings of the 17th Workshop on Algorithm Engineering and Experiments, 2015, pp. 173-187, https://doi.org/10.1137/1.9781611973754.15. · Zbl 1430.05125
[15] T. N. Dinh, Y. Xuan, M. T. Thai, P. M. Pardalos, and T. Znati, On new approaches of assessing network vulnerability: Hardness and approximation, IEEE/ACM Trans. Networking, 20 (2012), pp. 609-619, https://doi.org/10.1109/TNET.2011.2170849.
[16] Y. M. Erusalimskii and G. G. Svetlov, Bijoin points, bibridges, and biblocks of directed graphs, Cybernetics, 16 (1980), pp. 41-44, https://doi.org/10.1007/BF01099359. · Zbl 0462.05034
[17] W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan, Finding dominators via disjoint set union, J. Discrete Algorithms, 23 (2013), pp. 2-20, https://doi.org/10.1016/j.jda.2013.10.003. · Zbl 1294.05148
[18] H. N. Gabow, A Poset Approach to Dominator Computation, Unpublished manuscript, 2013.
[19] L. Georgiadis, T. D. Hansen, G. F. Italiano, S. Krinninger, and N. Parotsidis, Decremental data structures for connectivity and dominators in directed graphs, in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, eds., LIPIcs Leibniz Int. Proc. Inform. 80, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany, 2017, pp. 42:1-42:15, https://doi.org/10.4230/LIPIcs.ICALP.2017.42. · Zbl 1441.68184
[20] L. Georgiadis, G. F. Italiano, A. Karanasiou, C. Papadopoulos, and N. Parotsidis, Sparse certificates for 2-connectivity in directed graphs, Theoret. Comput. Sci., 698 (2017), pp. 40-66, https://doi.org/10.1016/j.tcs.2017.06.015. · Zbl 1380.05185
[21] L. Georgiadis, G. F. Italiano, A. Karanasiou, N. Parotsidis, and N. Paudel, Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: An experimental study, in Proceedings 20th Workshop on Algorithm Engineering and Experiments, 2018, pp. 169-183, https://doi.org/10.1137/1.9781611975055.15. · Zbl 1430.68210
[22] L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis, 2-edge connectivity in directed graphs, ACM Trans. Algorithms, 13 (2016), pp. 9:1-9:24, https://doi.org/10.1145/2968448. · Zbl 1451.05092
[23] L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis, 2-vertex connectivity in directed graphs, Inform. Comput., 261 (2018), pp. 248-264, https://doi.org/10.1016/j.ic.2018.02.007. · Zbl 1395.68209
[24] L. Georgiadis, G. F. Italiano, and N. Parotsidis, Incremental strong connectivity and 2-connectivity in directed graphs, in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, 2018. · Zbl 1485.68083
[25] L. Georgiadis, G. F. Italiano, and N. Parotsidis, Incremental 2-edge-connectivity in directed graphs, in Proceedings of ICALP, 2016, pp. 49:1-49:15, https://doi.org/10.4230/LIPIcs.ICALP.2016.49. · Zbl 1388.05178
[26] L. Georgiadis and R. E. Tarjan, Dominator tree certification and divergent spanning trees, ACM Trans. Algorithms, 12 (2015), pp. 11:1-11:42, https://doi.org/10.1145/2764913. · Zbl 1398.68396
[27] J. Gunawardena, A linear framework for time-scale separation in nonlinear biochemical systems, PLoS One, 7 (2012), e36321, https://doi.org/10.1371/journal.pone.0036321.
[28] D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13 (1984), pp. 338-55, https://doi.org/10.1137/0213024. · Zbl 0535.68022
[29] M. Henzinger, S. Krinninger, and V. Loitzenbauer, Finding 2-edge and 2-vertex strongly connected components in quadratic time, in Proceedings of ICALP, 2015, pp. 713-724, https://doi.org/10.1007/978-3-662-47672-7_58. · Zbl 1410.05203
[30] M. Henzinger, A. Lincoln, S. Neumann, and V. V. Williams, Conditional Hardness for Sensitivity Problems, in Proceedings of the 8th Innovations in Theoretical Computer Science Conference, C. H. Papadimitriou, ed., LIPIcs Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 26:1-26:31, https://doi.org/10.4230/LIPIcs.ITCS.2017.26. · Zbl 1402.68075
[31] G. F. Italiano, L. Laura, and F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoret. Comput. Sci., 447 (2012), pp. 74-84, https://doi.org/10.1016/j.tcs.2011.11.011. · Zbl 1245.05128
[32] R. Jaberi, Computing the \(2\)-blocks of directed graphs, RAIRO Theor. Inform. Appl., 49 (2015), pp. 93-119, https://doi.org/10.1051/ita/2015001. · Zbl 1342.05055
[33] V. King and G. Sagert, A fully dynamic algorithm for maintaining the transitive closure, J. Comput. System Sci., 65 (2002), pp. 150-167, https://doi.org/10.1006/jcss.2002.1883. · Zbl 1020.68106
[34] V. Krebs, Uncloaking terrorist networks, First Monday, 7 (2002), https://doi.org/10.5210/fm.v7i4.941.
[35] M. Lalou, M. A. Tahraoui, and H. Kheddouci, The critical node detection problem in networks: A survey, Comput. Sci. Rev., 28 (2018), pp. 92-117, https://doi.org/10.1016/j.cosrev.2018.02.002. · Zbl 1387.68186
[36] T. Lengauer and R. E. Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Trans. Program. Languages Systems, 1 (1979), pp. 121-141, https://doi.org/10.1145/357062.357071. · Zbl 0449.68024
[37] E. S. Lowry and V. W. Medlock, Object code optimization, Comm. ACM, 12 (1969), pp. 13-22, https://doi.org/10.1145/362835.362838.
[38] S. Makino, An algorithm for finding all the k-components of a digraph, Int. J. Comput. Math., 24 (1988), pp. 213-221, https://doi.org/10.1080/00207168808803645. · Zbl 0658.68075
[39] M. Mihalák, P. Uznański, and P. Yordanov, Prime factorization of the Kirchhoff polynomial: Compact enumeration of arborescences, in Proceedings of the 13th Workshop on Analytic Algorithmics and Combinatorics, 2016, pp. 93-105, https://doi.org/10.1137/1.9781611974324.10. · Zbl 1433.05161
[40] H. Nagamochi and T. Watanabe, Computing k-edge-connected components of a multigraph, IEICE Trans. Fundam. Electron., Commun. Comput. Sci., E76-A.4 (1993), pp. 513-517.
[41] N. Paudel, L. Georgiadis, and G. F. Italiano, Computing critical nodes in directed graphs, ACM J. Experimental Algorithmics, 23 (2018), pp. 2.2:1-2.2:24, https://doi.org/10.1145/3228332. · Zbl 1430.68234
[42] R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146-160, https://doi.org/10.1137/0201010. · Zbl 0251.05107
[43] R. E. Tarjan, Finding dominators in directed graphs, SIAM J. Comput., 3 (1974), pp. 62-89, https://doi.org/10.1137/0203006. · Zbl 0296.68030
[44] R. E. Tarjan, Efficiency of a good but not linear set union algorithm, J. ACM, 22 (1975), pp. 215-225, https://doi.org/10.1145/321879.321884. · Zbl 0307.68029
[45] R. E. Tarjan, Edge-disjoint spanning trees and depth-first search, Acta Inform., 6 (1976), pp. 171-85, https://doi.org/10.1007/BF00268499. · Zbl 0307.05104
[46] M. Ventresca and D. Aleman, Efficiently identifying critical nodes in large complex networks, Comput. Social Networks, 2 (2015), 6, https://doi.org/10.1186/s40649-015-0010-y.
[47] J. Westbrook and R. E. Tarjan, Maintaining bridge-connected and biconnected components on-line, Algorithmica, 7 (1992), pp. 433-464, https://doi.org/10.1007/BF01758773. · Zbl 0748.68045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.