Detecting critical node structures on graphs: A mathematical programming approach. Issue 1 (19th September 2018)

• Record Type: Journal Article
• Authors: Walteros, Jose L.; Veremyev, Alexander; Pardalos, Panos M.; Pasiliao, Eduardo L.
• Is Part Of: Networks. Volume 73:Issue 1(2019)
• Page Start: 48
• Page End: 88
• Publication Date: 2018-09-19
• Subjects: branch‐price‐and‐cut -- combinatorial optimization -- critical node problem -- graph partitioning -- mixed‐integer programming -- network interdiction; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21834
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We consider the problem of detecting a collection of critical node structures of a graph whose deletion results in the maximum deterioration of the graph's connectivity. The proposed approach is aimed to generalize other existing models whose scope is restricted to removing individual and unrelated nodes. We consider two common metrics to quantify the connectivity of the residual graph: the total number of connected node pairs and the size of the largest connected component. We first discuss the computational complexity of the problem and then introduce a general mixed‐integer linear formulation, which depending on the kind of node structures, may have an exponentially large number of variables and constraints. To solve this potentially large model, we develop a branch‐price‐and‐cut framework, along with some valid inequalities and preprocessing algorithms to strengthen the formulation and reduce the overall execution time. We use the proposed approach to solve the problem for the cases, where the node structures form cliques or stars and provide further directions on how to extend the framework for detecting other kinds of critical structures as well. Finally, we test the quality of our approach by solving a collection of real‐life and randomly generated instances with various configurations, analyze the benefits of our model, and propose further enhancements.