{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:58Z","timestamp":1740122458650,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T00:00:00Z","timestamp":1715990400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T00:00:00Z","timestamp":1715990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10878-024-01173-3","type":"journal-article","created":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T18:01:32Z","timestamp":1716055292000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The critical node game"],"prefix":"10.1007","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5447-6245","authenticated-orcid":false,"given":"Gabriele","family":"Dragotto","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0261-815X","authenticated-orcid":false,"given":"Amine","family":"Boukhtouta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9269-633X","authenticated-orcid":false,"given":"Andrea","family":"Lodi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4393-3014","authenticated-orcid":false,"given":"Mehdi","family":"Taobane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,18]]},"reference":[{"issue":"16\u201317","key":"1173_CR1","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1016\/j.dam.2013.03.021","volume":"161","author":"B Addis","year":"2013","unstructured":"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. Disc Appl Math 161(16\u201317):2349\u20132360. https:\/\/doi.org\/10.1016\/j.dam.2013.03.021. (ISSN 0166218X)","journal-title":"Disc Appl Math"},{"issue":"7","key":"1173_CR2","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.cor.2008.08.016","volume":"36","author":"A Arulselvan","year":"2009","unstructured":"Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput Oper Res 36(7):2193\u20132200. https:\/\/doi.org\/10.1016\/j.cor.2008.08.016. (ISSN 03050548)","journal-title":"Comput Oper Res"},{"issue":"6","key":"1173_CR3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0010-4825(87)90060-6","volume":"17","author":"N Assimakopoulos","year":"1987","unstructured":"Assimakopoulos N (1987) A network interdiction model for hospital infection control. Comput Biol Med 17(6):413\u2013422. https:\/\/doi.org\/10.1016\/0010-4825(87)90060-6. (ISSN 00104825)","journal-title":"Comput Biol Med"},{"issue":"2","key":"1173_CR4","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1287\/opre.2020.2014","volume":"69","author":"A Baggio","year":"2021","unstructured":"Baggio A, Carvalho M, Lodi A, Tramontani A (2021) Multilevel approaches for the critical node problem. Oper Res 69(2):486\u2013508. https:\/\/doi.org\/10.1287\/opre.2020.2014. (ISSN 0030-364X, 1526-5463)","journal-title":"Oper Res"},{"issue":"2","key":"1173_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-6377(89)90003-5","volume":"8","author":"MO Ball","year":"1989","unstructured":"Ball MO, Golden BL, Vohra RV (1989) Finding the most vital arcs in a network. Oper Res Lett 8(2):73\u201376. https:\/\/doi.org\/10.1016\/0167-6377(89)90003-5. (ISSN 01676377)","journal-title":"Oper Res Lett"},{"issue":"17","key":"1173_CR6","doi-asserted-by":"publisher","first-page":"1933","DOI":"10.1016\/j.dam.2011.06.023","volume":"159","author":"C Bazgan","year":"2011","unstructured":"Bazgan C, Toubaline S, Tuza Z (2011) The most vital nodes with respect to independent set and vertex cover. Disc Appl Math 159(17):1933\u20131946. https:\/\/doi.org\/10.1016\/j.dam.2011.06.023. (ISSN 0166218X)","journal-title":"Disc Appl Math"},{"key":"1173_CR7","unstructured":"Bertsimas D, den Hertog D (2022) Robust and adaptive optimization. Dynamic ideas LLC, 1st edn. https:\/\/www.dynamic-ideas.com\/books\/robust-and-adaptive-optimization"},{"key":"1173_CR8","doi-asserted-by":"publisher","unstructured":"Borgatti SP (2003) Identifying sets of key players in a network. In: IEMC \u201903 Proceedings of the managing technologically driven organizations: the human side of innovation and change (IEEE Cat. No.03CH37502), pp 127\u2013131, Cambridge, MA, USA. IEEE. https:\/\/doi.org\/10.1109\/KIMAS.2003.1245034 ISBN 978-0-7803-7958-9","DOI":"10.1109\/KIMAS.2003.1245034"},{"key":"1173_CR9","doi-asserted-by":"publisher","unstructured":"Boukhtouta A, Madi T, Pourzandi M, Alameddine H (2022) Cloud native applications profiling using a graph neural networks approach. In: 2022 IEEE future networks world forum (FNWF), pp 220\u2013227. IEEE. https:\/\/doi.org\/10.1109\/KIMAS.2003.1245034","DOI":"10.1109\/KIMAS.2003.1245034"},{"issue":"6","key":"1173_CR10","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/FNWF55208.2022.00046","volume":"36","author":"G Brown","year":"2006","unstructured":"Brown G, Carlyle M, Salmer\u00f3n J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530\u2013544. https:\/\/doi.org\/10.1109\/FNWF55208.2022.00046. (ISSN 0092-2102, 1526-551X)","journal-title":"Interfaces"},{"key":"1173_CR11","doi-asserted-by":"publisher","unstructured":"Carvalho M, Lodi A, Pedroso JP (2018) Existence of nash equilibria on integer programming games. In: Ismael A, Vaz F, Almeida JP, Oliveira JF, Pinto AA (eds) Operational research, vol 223, pp 11\u201323. Springer International Publishing, Cham.https:\/\/doi.org\/10.1007\/978-3-319-71583-4_2 ISBN 978-3-319-71582-7 978-3-319-71583-4","DOI":"10.1007\/978-3-319-71583-4_2"},{"key":"1173_CR12","doi-asserted-by":"publisher","unstructured":"Carvalho M, Dragotto G, Lodi A, Sankaranarayanan S (2023) Integer programming games: a gentle computational overview, chap 2, pp 31\u201351. https:\/\/doi.org\/10.1287\/educ.2023.0260 INFORMS","DOI":"10.1287\/educ.2023.0260"},{"issue":"2","key":"1173_CR13","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/TIFS.2009.2019154","volume":"4","author":"L Chen","year":"2009","unstructured":"Chen L, Leneutre J (2009) A game theoretical framework on intrusion detection in heterogeneous networks. IEEE Trans Inf Forensics Security 4(2):165\u2013178. https:\/\/doi.org\/10.1109\/TIFS.2009.2019154","journal-title":"IEEE Trans Inf Forensics Security"},{"key":"1173_CR14","doi-asserted-by":"crossref","unstructured":"Cohen R, Havlin S, ben Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett, 91(24):247901. https:\/\/journals.aps.org\/prl\/abstract\/10.1103\/PhysRevLett.91.247901 ISSN 0031-9007, 1079-7114","DOI":"10.1103\/PhysRevLett.91.247901"},{"issue":"4","key":"1173_CR15","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/s10878-007-9071-7","volume":"14","author":"CW Commander","year":"2007","unstructured":"Commander CW, Pardalos PM, Ryabchenko V, Uryasev S, Zrazhevsky G (2007) The wireless network jamming problem. J Combinat Opt 14(4):481\u2013498. https:\/\/doi.org\/10.1007\/s10878-007-9071-7. (ISSN 1382-6905, 1573-2886)","journal-title":"J Combinat Opt"},{"key":"1173_CR16","unstructured":"MITRE Corporation (2023) MITRE ATT &CK. https:\/\/attack.mitre.org"},{"issue":"12","key":"1173_CR17","doi-asserted-by":"publisher","first-page":"1766","DOI":"10.1016\/j.cor.2011.02.016","volume":"38","author":"M Di Summa","year":"2011","unstructured":"Di Summa M, Grosso A, Locatelli M (2011) Complexity of the critical node problem over trees. Comput Oper Res 38(12):1766\u20131774. https:\/\/doi.org\/10.1016\/j.cor.2011.02.016. (ISSN 03050548)","journal-title":"Comput Oper Res"},{"key":"1173_CR18","unstructured":"Dragotto Gabriele (2022) Mathematical programming games. PhD thesis, Polytechnique Montr\u00e9al. https:\/\/publications.polymtl.ca\/10220\/"},{"issue":"5","key":"1173_CR19","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1287\/ijoc.2022.0282","volume":"35","author":"G Dragotto","year":"2023","unstructured":"Dragotto G, Scatamacchia R (2023) The ZERO regrets algorithm: optimizing over pure nash equilibria via integer programming. INFORMS J Comput 35(5):1143\u20131160. https:\/\/doi.org\/10.1287\/ijoc.2022.0282","journal-title":"INFORMS J Comput"},{"key":"1173_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.geb.2012.12.007","volume":"79","author":"M Dziubi\u0144ski","year":"2013","unstructured":"Dziubi\u0144ski M, Goyal S (2013) Network design and defence. Games Econ Behav 79:30\u201343. https:\/\/doi.org\/10.1016\/j.geb.2012.12.007","journal-title":"Games Econ Behav"},{"key":"1173_CR21","unstructured":"Finbow S, MacGillivray G (2009) The firefighter problem: a survey of results, directions and questions. Australas J Comb 43:55\u201377. https:\/\/ajc.maths.uq.edu.au\/pdf\/43\/ajc_v43_p057.pdf"},{"issue":"2","key":"1173_CR22","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1287\/ijoc.2018.0831","volume":"31","author":"M Fischetti","year":"2019","unstructured":"Fischetti M, Ljubi\u0107 I, Monaci M, Sinnl M (2019) Interdiction games and monotonicity, with application to knapsack problems. INFORMS J Comput 31(2):390\u2013410. https:\/\/doi.org\/10.1287\/ijoc.2018.0831. (ISSN 1091-9856, 1526-5528)","journal-title":"INFORMS J Comput"},{"issue":"4","key":"1173_CR23","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1093\/restud\/rdu013","volume":"81","author":"S Goyal","year":"2014","unstructured":"Goyal S, Vigier A (2014) Attack, defence, and contagion in networks. Rev Econ Stud 81(4):1518\u20131542. https:\/\/doi.org\/10.1093\/restud\/rdu013","journal-title":"Rev Econ Stud"},{"key":"1173_CR24","doi-asserted-by":"publisher","unstructured":"He Wei, Xia Chunhe, Wang Haiquan, Zhang Cheng, Ji Yi (2008) A game theoretical attack-defense model oriented to network security risk assessment. In: 2008 International conference on computer science and software engineering, vol 6, pp 498\u2013504. IEEE. https:\/\/doi.org\/10.1109\/CSSE.2008.1651","DOI":"10.1109\/CSSE.2008.1651"},{"issue":"3","key":"1173_CR25","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/net.21948","volume":"76","author":"P Hosteins","year":"2020","unstructured":"Hosteins P, Scatamacchia R (2020) The stochastic critical node problem over trees. Networks 76(3):381\u2013401. https:\/\/doi.org\/10.1002\/net.21948. (ISSN 0028-3045, 1097-0037)","journal-title":"Networks"},{"issue":"2","key":"1173_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.10039","volume":"40","author":"E Israeli","year":"2002","unstructured":"Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97\u2013111. https:\/\/doi.org\/10.1002\/net.10039. (ISSN 0028-3045, 1097-0037)","journal-title":"Networks"},{"key":"1173_CR27","doi-asserted-by":"publisher","unstructured":"Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: Goos G, Hartmanis J, van Leeuwen J, Meinel C, Tison S, (eds), STACS 99, vol 1563, pp 404\u2013413. Springer, Berlin. https:\/\/doi.org\/10.1007\/3-540-49116-3_38 ISBN 978-3-540-65691-3 978-3-540-49116-3","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"6","key":"1173_CR28","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1287\/opre.1110.0964","volume":"59","author":"M K\u00f6ppe","year":"2011","unstructured":"K\u00f6ppe M, Ryan CT, Queyranne M (2011) Rational generating functions and integer programming games. Oper Res 59(6):1445\u20131460. https:\/\/doi.org\/10.1287\/opre.1110.0964. (ISSN 0030-364X, 1526-5463)","journal-title":"Oper Res"},{"key":"1173_CR29","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.cosrev.2018.02.002","volume":"28","author":"M Lalou","year":"2018","unstructured":"Lalou M, Tahraoui MA, Kheddouci H (2018) The critical node detection problem in networks: a survey. Comput Sci Rev 28:92\u2013117. https:\/\/doi.org\/10.1016\/j.cosrev.2018.02.002. (ISSN 15740137)","journal-title":"Comput Sci Rev"},{"key":"1173_CR30","unstructured":"Nabli A, Carvalho M (2020) Curriculum learning for multilevel budgeted combinatorial problems. In: Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H (eds), Adv Neural Inf Process Syst, vol 33, pp 7044\u20137056. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/4eb7d41ae6005f60fe401e56277ebd4e-Abstract.html"},{"issue":"1","key":"1173_CR31","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash JF (1950) Equilibrium points in n-person games. Proc Nat Acad Sci United States Am 36(1):48\u201349. https:\/\/doi.org\/10.1073\/pnas.36.1.48","journal-title":"Proc Nat Acad Sci United States Am"},{"issue":"5","key":"1173_CR32","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1287\/mnsc.21.5.531","volume":"21","author":"HD Ratliff","year":"1975","unstructured":"Ratliff HD, Sicilia GT, Lubore SH (1975) Finding the n most vital links in flow networks. Manage Sci 21(5):531\u2013539. https:\/\/doi.org\/10.1287\/mnsc.21.5.531. (ISSN 0025-1909, 1526-5501)","journal-title":"Manage Sci"},{"key":"1173_CR33","doi-asserted-by":"publisher","unstructured":"Roy S, Ellis C, Shiva S, Dasgupta D, Shandilya V, Wu Q (2010) A survey of game theory as applied to network security. In: 2010 43rd Hawaii international conference on system sciences, pp 1\u201310, Honolulu, Hawaii, USA. IEEE. https:\/\/doi.org\/10.1109\/HICSS.2010.35 ISBN 978-1-4244-5509-6","DOI":"10.1109\/HICSS.2010.35"},{"issue":"2","key":"1173_CR34","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/net.20464","volume":"60","author":"S Shen","year":"2012","unstructured":"Shen S, Smith JC (2012) Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2):103\u2013119. https:\/\/doi.org\/10.1002\/net.20464. (ISSN 00283045)","journal-title":"Networks"},{"issue":"3","key":"1173_CR35","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.disopt.2012.07.001","volume":"9","author":"S Shen","year":"2012","unstructured":"Shen S, Smith JC, Goli R (2012) Exact interdiction models and algorithms for disconnecting networks via node deletions. Disc Opt 9(3):172\u2013188. https:\/\/doi.org\/10.1016\/j.disopt.2012.07.001. (ISSN 15725286)","journal-title":"Disc Opt"},{"issue":"5","key":"1173_CR36","doi-asserted-by":"publisher","first-page":"2634","DOI":"10.1287\/ijoc.2022.1196","volume":"34","author":"K Tan\u0131nm\u0131\u015f","year":"2022","unstructured":"Tan\u0131nm\u0131\u015f K, Sinnl M (2022) A branch-and-cut algorithm for submodular interdiction games. INFORMS J Comput 34(5):2634\u20132657. https:\/\/doi.org\/10.1287\/ijoc.2022.1196. (ISSN 1091-9856, 1526-5528)","journal-title":"INFORMS J Comput"},{"key":"1173_CR37","doi-asserted-by":"publisher","unstructured":"Tao Z, Zhongqian F, Binghong W (2006) Epidemic dynamics on complex networks. Prog Nat Sci 16(5):452\u2013457. https:\/\/doi.org\/10.1080\/10020070612330019","DOI":"10.1080\/10020070612330019"},{"issue":"1","key":"1173_CR38","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10878-014-9730-4","volume":"28","author":"A Veremyev","year":"2014","unstructured":"Veremyev A, Prokopyev OA, Pasiliao EL (2014) An integer programming framework for critical elements detection in graphs. J Combinat Opt 28(1):233\u2013273. https:\/\/doi.org\/10.1007\/s10878-014-9730-4. (ISSN 1382-6905, 1573-2886)","journal-title":"J Combinat Opt"},{"issue":"13","key":"1173_CR39","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1016\/j.dam.2010.04.008","volume":"158","author":"R Zenklusen","year":"2010","unstructured":"Zenklusen R (2010) Network flow interdiction on planar graphs. Disc Appl Math 158(13):1441\u20131455. https:\/\/doi.org\/10.1016\/j.dam.2010.04.008. (ISSN 0166218X)","journal-title":"Disc Appl Math"},{"issue":"15","key":"1173_CR40","doi-asserted-by":"publisher","first-page":"1676","DOI":"10.1016\/j.dam.2010.06.006","volume":"158","author":"R Zenklusen","year":"2010","unstructured":"Zenklusen R (2010) Matching interdiction. Disc Appl Math 158(15):1676\u20131690. https:\/\/doi.org\/10.1016\/j.dam.2010.06.006. (ISSN 0166218X)","journal-title":"Disc Appl Math"},{"issue":"6\u20137","key":"1173_CR41","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1016\/j.orl.2014.07.010","volume":"42","author":"R Zenklusen","year":"2014","unstructured":"Zenklusen R (2014) Connectivity interdiction. Oper Res Lett 42(6\u20137):450\u2013454. https:\/\/doi.org\/10.1016\/j.orl.2014.07.010. (ISSN 01676377)","journal-title":"Oper Res Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01173-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01173-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01173-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T14:40:43Z","timestamp":1721659243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01173-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,18]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1173"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01173-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,5,18]]},"assertion":[{"value":"12 April 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Most of this work was conducted when the first and third authors were members of the Canada Excellence Research Chair in \u201cData Science for Real-time Decision-making\u201d (CERC) at Polytechnique Montr\u00e9al. This work has also been supported by the \u201cGame Theoretic Security Posture Modeling for Cloud Native Applications\u201d University-Industry agreement between Polytechnique Montr\u00e9al and Ericsson Canada. The first and fourth authors received financial support from CERC and Ericsson Canada. The second author is an employee of Ericsson Canada. All the authors are involved in a provisional patent of Telefonaktiebolaget LM Ericsson, a corporation duly organized under and pursuant to the laws of Sweden and having its principal place of business at SE-164 83 Stockholm, Sweden.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"74"}}