Abstract
In this paper we apply a region growing bicriteria approximation algorithm of [5] for determining solutions to the critical node detection problem. This problem takes as input a number \(K\) and a connected, unweighted graph, and has the goal of selecting \(\le K\) vertices to remove such that the residual network has minimum pairwise connectivity. This problem has numerous applications, including those in network security, disease mitigation, marketing and antiterrorism. The algorithm achieves an \(\mathcal {O}(\log n)\) approximation on the number of vertices needed to attain an \(\mathcal {O}(1)\) bound on the objective function. Four random graph models and four real-world networks from different application areas are used to demonstrate that the algorithm performs within the predicted bounds.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Addis, B., Di Summa, M., Grosso, A.: Complexity results and polynomial algorithms for the case of bounded treewidth. Discrete Appl. Math. 161(16–17), 2349–2360 (2013)
Arulselvan, A., Commander, C.W., Elefteriadou, L., Pardalos, P.M.: Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7), 2193–2200 (2009)
Arulselvan, A., Commander, C.W., Pardalos, P.M., Shylo, O.: Managing network risk via critical node identification. In: Gulpinar, N., Rustem, B. (eds.) Risk Management in Telecommunication Networks. Springer, Heidelberg (2011)
Aspnes, J., Chang, K., Yampolskiy, A.: Inoculation strategies for victims of viruses and the sum-of-squares partition problem. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pp. 43–52. Society for Industrial and Applied Mathematics (2005)
Chen, P., David, M., Kempe, D.: Better vaccination strategies for better people. In: Proceedings of the 11th ACM Conference on Electronic Commerce, pp. 179–188. ACM (2010)
Di Summa, M., Grosso, A., Locatelli, M.: Complexity of the critical node problem over trees. Comput. Oper. Res. 38(12), 1766–1774 (2011)
Di Summa, M., Grosso, A., Locatelli, M.: Branch and cut algorithms for detecting critical nodes in undirected graphs. Comput. Optim. Appl. 53(3), 649–680 (2012)
Dinh, T.N., Xuan, Y., Thai, M.T., Pardalos, P.M., Znati, T.: On new approaches of assessing network vulnerability: hardness and approximation. IEEE/ACM Trans. Netw. 20(2), 609–619 (2012)
Garg, N., Vazirani, V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25, 698–707 (1993)
Krebs, V.: Uncloaking terrorist networks, first monday (2001). http://www.orgnet.com/hijackers.html
Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 422–431. IEEE Computer Society (1988)
Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)
Venkatesan, K., Rual, J.F., Vazquez, A., Stelzl, U., Lemmens, I., Hirozane-Kishikawa, T., Hao, T., Zenkner, M., Xin, X., Goh, K., Yildirim, M.A., Simonis, N., Heinzmann, K., Gebreab, F., Sahalie, J.M., Cevik, S., Simon, C., de Smet, A., Dann, E., Smolyar, A., Vinayagam, A., Yu, H., Szeto, D., Borick, H., Dricot, A., Klitgord, N., Murray, R., Lin, C., Lalowski, M., Timm, J., Rau, K., Boone, C., Braun, P., Cusick, M., Roth, F., Hill, D., Tavernier, J., Wanker, E., Barabasi, A.L., Vidal, M.: An empirical framework for binary interactome mapping. Nat. Methods 6(1), 83–90 (2009)
Ventresca, M.: Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Comput. Oper. Res. 39(11), 2763–2775 (2012)
Ventresca, M., Aleman, D.: A derandomized approximation algorithm for the critical node detection problem. Comput. Oper. Res. 43, 261–270 (2014)
Ventresca, M., Aleman, D.: A randomized algorithm with local search for containment of pandemic disease spread. Comput. Oper. Res. 48, 11–19 (2014)
Veremyev, A., Boginski, V., Pasiliao, E.L.: Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8(4), 1245–1259 (2014)
Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: An integer programming framework for critical elements detection in graphs. J. Comb. Optim. 28(1), 233–273 (2014)
Veremyev, A., Boginski, V., Pasiliao, E.L.: Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8, 1245–1259 (2014)
von Mering, C., Krause, R., Snel, B., Cornell, M., Oliver, S., Fields, S., Bork, P.: Comparative assessment of large-scale data sets of protein-protein interactions. Nature 417, 399–403 (2002)
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ventresca, M., Aleman, D. (2014). A Region Growing Algorithm for Detecting Critical Nodes. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_44
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_44
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)