×

Solving the distance-based critical node problem. (English) Zbl 07552209

Summary: In critical node problems, the task is to identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, for example, for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having fewer than 1,000 nodes. In this paper, we consider a variant of this problem in which the task is to delete \(b\) nodes so as to minimize the number of node pairs that remain connected by a path of length at most \(k\). With the techniques developed in this paper, instances with up to 17,000 nodes can be solved exactly. We introduce two integer programming formulations for this problem (thin and path-like) and compare them with an existing recursive formulation. Although the thin formulation generally has an exponential number of constraints, it admits an efficient separation routine. Also helpful is a new, more general preprocessing procedure that, on average, fixes three times as many variables than before.
Summary of contribution: In this paper, we consider a distance-based variant of the critical node problem in which the task is to delete \(b\) nodes so as to minimize the number of node pairs that remain connected by a path of length at most \(k\). This problem is motivated by applications in social networks, telecommunications, and transportation networks. In our paper, we aim to solve large-scale instances of this problem. Standard out-of-the-box approaches are unable to solve such instances, requiring new integer programming models, methodological contributions, and other computational insights. For example, we propose an algorithm for finding a maximum independent set of simplicial nodes that runs in time \(O(nm)\) that we use in a preprocessing procedure; we also prove that the separation problem associated with one of our integer programming models is NP-hard. We apply our branch-and-cut implementation to real-life networks from a variety of domains and observe speedups over previous approaches.

MSC:

90-XX Operations research, mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addis B, Di Summa M, Grosso A (2013) Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discrete Appl. Math. 161(16-17):2349-2360.Crossref, Google Scholar · Zbl 1285.05042 · doi:10.1016/j.dam.2013.03.021
[2] Addis B, Aringhieri R, Grosso A, Hosteins P (2016) Hybrid constructive heuristics for the critical node problem. Ann. Oper. Res. 238(1-2):637-649.Crossref, Google Scholar · Zbl 1334.90185 · doi:10.1007/s10479-016-2110-y
[3] Alozie GU, Arulselvan A, Akartunali K, Pasiliao Jr EL (2021) Efficient methods for the distance-based critical node detection problem in complex networks. Comput. Oper. Res. 131:105254.Crossref, Google Scholar · Zbl 1510.90273 · doi:10.1016/j.cor.2021.105254
[4] Aringhieri R, Grosso A, Hosteins P, Scatamacchia R (2019) Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem. Discrete Appl. Math. 253:103-121.Crossref, Google Scholar · Zbl 1401.05089 · doi:10.1016/j.dam.2017.12.035
[5] Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7):2193-2200.Crossref, Google Scholar · Zbl 1158.90411 · doi:10.1016/j.cor.2008.08.016
[6] Baier G, Erlebach T, Hall A, Köhler E, Kolman P, Pangrác O, Schilling H, Skutella M (2010) Length-bounded cuts and flows. ACM Trans. Algorithms 7(1):1-27 (TALG).Crossref, Google Scholar · Zbl 1295.68119 · doi:10.1145/1868237.1868241
[7] Balas E, Fischetti M (1996) On the monotonization of polyhedra. Math. Programming 78(1):59-84.Crossref, Google Scholar · Zbl 0890.90153 · doi:10.1007/BF02614506
[8] Batagelj V, Mrvar A (2006) Pajek datasets. Accessed April 12, 2020, http://vlado.fmf.uni-lj.si/pub/networks/data/.Google Scholar
[9] Boginski V, Commander CW (2009) Identifying Critical Nodes in Protein-Protein Interaction Networks. Clustering Challenges in Biological Networks (World Scientific, Singapore), 153-167.Google Scholar
[10] Borgatti SP (2006) Identifying sets of key players in a social network. Comput. Math. Organ. Theory 12(1):21-34.Crossref, Google Scholar · Zbl 1198.91180 · doi:10.1007/s10588-006-7084-x
[11] Brandes U (2001) A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2):163-177.Crossref, Google Scholar · Zbl 1051.91088 · doi:10.1080/0022250X.2001.9990249
[12] Buchanan A, Sung JS, Butenko S, Pasiliao EL (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J. Comput. 27(1):178-188.Link, Google Scholar · Zbl 1327.90348
[13] Carvajal R, Constantino M, Goycoolea M, Vielma JP, Weintraub A (2013) Imposing connectivity constraints in forest planning models. Oper. Res. 61(4):824-836.Link, Google Scholar · Zbl 1291.90341
[14] Charkhgard H, Subramanian V, Silva W, Das TK (2018) An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections. Discrete Optim. 30:144-167.Crossref, Google Scholar · Zbl 1454.92028 · doi:10.1016/j.disopt.2018.06.005
[15] Cohen R, Havlin S, Ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91(24):247901.Crossref, Google Scholar · doi:10.1103/PhysRevLett.91.247901
[16] Commander CW, Pardalos PM, Ryabchenko V, Uryasev S, Zrazhevsky G (2007) The wireless network jamming problem. J. Combin. Optim. 14(4):481-498.Crossref, Google Scholar · Zbl 1149.90124 · doi:10.1007/s10878-007-9071-7
[17] Conforti M, Cornuéjols G, Zambelli G (2013) Extended formulations in combinatorial optimization. Ann. Oper. Res. 204(1):97-143.Crossref, Google Scholar · Zbl 1273.90170 · doi:10.1007/s10479-012-1269-0
[18] Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans. Math. Software 38(1):1-25.Crossref, Google Scholar · Zbl 1365.65123 · doi:10.1145/2049662.2049663
[19] Di Summa M, Grosso A, Locatelli M (2011) Complexity of the critical node problem over trees. Comput. Oper. Res. 38(12):1766-1774.Crossref, Google Scholar · Zbl 1215.90016 · doi:10.1016/j.cor.2011.02.016
[20] Di Summa M, Grosso A, Locatelli M (2012) Branch and cut algorithms for detecting critical nodes in undirected graphs. Comput. Optim. Appl. 53(3):649-680.Crossref, Google Scholar · Zbl 1264.90170 · doi:10.1007/s10589-012-9458-y
[21] DIMACS-10 (2017) 10th DIMACS implementation challenge: Graph partitioning and graph clustering. Accessed April 12, 2020, http://www.cc.gatech.edu/dimacs10/downloads.shtml.Google Scholar
[22] Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017) Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Programming Comput. 9(2):203-229.Crossref, Google Scholar · Zbl 1387.90132 · doi:10.1007/s12532-016-0111-0
[23] Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35-41.Crossref, Google Scholar · doi:10.2307/3033543
[24] Garey MR, Johnson DS (1979) Computers and Intractability (W.H. Freeman and Company, New York).Google Scholar · Zbl 0411.68039
[25] Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer-Verlag, Berlin).Crossref, Google Scholar · Zbl 0837.05001 · doi:10.1007/978-3-642-78240-4
[26] Hooshmand F, Mirarabrazi F, MirHassani S (2020) Efficient Benders decomposition for distance-based critical node detection problem. Omega 93:102037.Crossref, Google Scholar · doi:10.1016/j.omega.2019.02.006
[27] Kutz M (2004) Handbook of Transportation Engineering, vol. 768 (McGraw-Hill, New York).Google Scholar
[28] Lalou M, Tahraoui MA, Kheddouci H (2018) The critical node detection problem in networks: A survey. Comput. Sci. Rev. 28:92-117.Crossref, Google Scholar · Zbl 1387.68186 · doi:10.1016/j.cosrev.2018.02.002
[29] Matisziw TC, Murray AT (2009) Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure. Comput. Oper. Res. 36(1):16-26.Crossref, Google Scholar · Zbl 1163.90441 · doi:10.1016/j.cor.2007.09.004
[30] Salemi H, Buchanan A (2020) Parsimonious formulations for low-diameter clusters. Math. Programming Comput. 12(3):493-528.Crossref, Google Scholar · Zbl 1452.90083 · doi:10.1007/s12532-020-00175-6
[31] Salemi H, Buchanan A (2021) Implementation of solving the distance-based critical node problem. Accessed April 12, 2020, https://github.com/halisalemi/DCNP.Google Scholar
[32] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 (Springer Science & Business Media, Berlin).Google Scholar · Zbl 1041.90001
[33] Shen Y, Nguyen NP, Xuan Y, Thai MT (2013) On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Trans. Networking 21(3):963-973.Crossref, Google Scholar · doi:10.1109/TNET.2012.2215882
[34] Stabler B, Bar-Gera H, Sall E (2019) Transportation networks for research. Accessed April 12, 2020, https://github.com/bstabler/TransportationNetworks.Google Scholar
[35] STOM-Group (2019) Hazmat network data. Accessed April 12, 2020, https://github.com/STOM-Group/Hazmat-Network-Data.Google Scholar
[36] Tao Z, Zhongqian F, Binghong W (2006) Epidemic dynamics on complex networks. Progress Natural Sci. 16(5):452-457.Crossref, Google Scholar · Zbl 1121.92063 · doi:10.1080/10020070612330019
[37] Validi H, Buchanan A (2020) The optimal design of low-latency virtual backbones. INFORMS J. Comput. 32(4):952-967.Abstract, Google Scholar · Zbl 1456.90040
[38] Veremyev A, Boginski V, Pasiliao EL (2014) Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8(4):1245-1259.Crossref, Google Scholar · Zbl 1292.90260 · doi:10.1007/s11590-013-0666-x
[39] Veremyev A, Prokopyev OA, Pasiliao EL (2015) Critical nodes for distance-based connectivity and related problems in graphs. Networks 66(3):170-195.Crossref, Google Scholar · doi:10.1002/net.21622
[40] Walteros JL, Pardalos PM (2012) Selected topics in critical element detection. Daras NJ, ed. Applications of Mathematics and Informatics in Military Science, Springer Optimization and Its Applications, vol. 71 (Springer, New York), 9-26.Crossref, Google Scholar · Zbl 1315.90060 · doi:10.1007/978-1-4614-4109-0_2
[41] Walteros JL, Veremyev A, Pardalos PM, Pasiliao EL (2019) Detecting critical node structures on graphs: A mathematical programming approach. Networks 73(1):48-88.Crossref, Google Scholar · Zbl 1407.90093 · doi:10.1002/net.21834
[42] Zachary WW (1977) An information flow model for conflict and fission in small groups. J. Anthropological Res. 33(4):452-473.Crossref, Google Scholar · doi:10.1086/jar.33.4.3629752
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.