Detecting critical node structures on graphs: A mathematical programming approach

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.