IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v53y2012i3p649-680.html
   My bibliography  Save this article

Branch and cut algorithms for detecting critical nodes in undirected graphs

Author

Listed:
  • Marco Di Summa
  • Andrea Grosso
  • Marco Locatelli

Abstract

In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • Marco Di Summa & Andrea Grosso & Marco Locatelli, 2012. "Branch and cut algorithms for detecting critical nodes in undirected graphs," Computational Optimization and Applications, Springer, vol. 53(3), pages 649-680, December.
    • Handle: RePEc:spr:coopap:v:53:y:2012:i:3:p:649-680
    DOI: 10.1007/s10589-012-9458-y
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-012-9458-y
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-012-9458-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Myung, Young-Soo & Kim, Hyun-joon, 2004. "A cutting plane algorithm for computing k-edge survivability of a network," European Journal of Operational Research, Elsevier, vol. 156(3), pages 579-589, August.
    2. Richard Wollmer, 1964. "Removing Arcs from a Network," Operations Research, INFORMS, vol. 12(6), pages 934-940, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    2. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    3. Joe Naoum-Sawaya & Christoph Buchheim, 2016. "Robust Critical Node Selection by Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 162-174, February.
    4. Mahdavi Pajouh, Foad & Walteros, Jose L. & Boginski, Vladimir & Pasiliao, Eduardo L., 2015. "Minimum edge blocker dominating set problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 16-26.
    5. Zhou, Yangming & Wang, Gezi & Hao, Jin-Kao & Geng, Na & Jiang, Zhibin, 2023. "A fast tri-individual memetic search approach for the distance-based critical node problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 540-554.
    6. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    7. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    8. T. N. Dinh & M. T. Thai & H. T. Nguyen, 2014. "Bound and exact methods for assessing link vulnerability in complex networks," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 3-24, July.
    9. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    10. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    11. Chen, Wei & Jiang, Manrui & Jiang, Cheng & Zhang, Jun, 2020. "Critical node detection problem for complex network in undirected weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 538(C).
    12. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    13. Alexander Veremyev & Konstantin Pavlikov & Eduardo L. Pasiliao & My T. Thai & Vladimir Boginski, 2019. "Critical nodes in interdependent networks with deterministic and probabilistic cascading failures," Journal of Global Optimization, Springer, vol. 74(4), pages 803-838, August.
    14. Gokhan Karakose & Ronald G. McGarvey, 2019. "Optimal Detection of Critical Nodes: Improvements to Model Structure and Performance," Networks and Spatial Economics, Springer, vol. 19(1), pages 1-26, March.
    15. Lordan, Oriol & Albareda-Sambola, Maria, 2019. "Exact calculation of network robustness," Reliability Engineering and System Safety, Elsevier, vol. 183(C), pages 276-280.
    16. Faramondi, Luca & Setola, Roberto & Panzieri, Stefano & Pascucci, Federica & Oliva, Gabriele, 2018. "Finding critical nodes in infrastructure networks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 20(C), pages 3-15.
    17. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    18. Ventresca, Mario & Harrison, Kyle Robert & Ombuki-Berman, Beatrice M., 2018. "The bi-objective critical node detection problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 895-908.
    19. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    20. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Starita, Stefano & Scaparra, Maria Paola, 2016. "Optimizing dynamic investment decisions for railway systems protection," European Journal of Operational Research, Elsevier, vol. 248(2), pages 543-557.
    2. Tony H. Grubesic & Timothy C. Matisziw & Alan T. Murray & Diane Snediker, 2008. "Comparative Approaches for Assessing Network Vulnerability," International Regional Science Review, , vol. 31(1), pages 88-112, January.
    3. Young‐Soo Myung & Hyun‐Joon Kim, 2007. "Network disconnection problems in a centralized network," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(7), pages 710-719, October.
    4. Alan Murray & Timothy Matisziw & Tony Grubesic, 2007. "Critical network infrastructure analysis: interdiction and system flow," Journal of Geographical Systems, Springer, vol. 9(2), pages 103-117, June.
    5. Annunziata Esposito Amideo & Stefano Starita & Maria Paola Scaparra, 2019. "Assessing Protection Strategies for Urban Rail Transit Systems: A Case-Study on the Central London Underground," Sustainability, MDPI, vol. 11(22), pages 1-21, November.
    6. Rocco S, Claudio M. & Ramirez-Marquez, José Emmanuel, 2009. "Deterministic network interdiction optimization via an evolutionary approach," Reliability Engineering and System Safety, Elsevier, vol. 94(2), pages 568-576.
    7. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    8. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    9. Karakose, Gokhan & McGarvey, Ronald G., 2018. "Capacitated path-aggregation constraint model for arc disruption in networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 225-238.
    10. Qian Ye & Hyun Kim, 2019. "Assessing network vulnerability of heavy rail systems with the impact of partial node failures," Transportation, Springer, vol. 46(5), pages 1591-1614, October.
    11. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    12. Nguyen, Di H. & Smith, J. Cole, 2022. "Network interdiction with asymmetric cost uncertainty," European Journal of Operational Research, Elsevier, vol. 297(1), pages 239-251.
    13. César Yajure & Darihelen Montilla & Jose Emmanuel Ramirez-Marquez & Claudio M Rocco S, 2013. "Network vulnerability assessment via bi-objective optimization with a fragmentation approach as proxy," Journal of Risk and Reliability, , vol. 227(6), pages 576-585, December.
    14. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    15. Rodríguez-Núñez, Eduardo & García-Palomares, Juan Carlos, 2014. "Measuring the vulnerability of public transport networks," Journal of Transport Geography, Elsevier, vol. 35(C), pages 50-63.
    16. Michael P. Atkinson & Lawrence M. Wein, 2008. "TECHNICAL NOTE---Spatial Queueing Analysis of an Interdiction System to Protect Cities from a Nuclear Terrorist Attack," Operations Research, INFORMS, vol. 56(1), pages 247-254, February.
    17. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    18. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    19. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    20. Rocco S., Claudio M. & Emmanuel Ramirez-Marquez, José & Salazar A., Daniel E., 2010. "Bi and tri-objective optimization in the deterministic network interdiction problem," Reliability Engineering and System Safety, Elsevier, vol. 95(8), pages 887-896.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:53:y:2012:i:3:p:649-680. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.