A Decomposition Approach for Solving Critical Clique Detection Problems

摘要

The problem of detecting critical elements in a network involves the identification of a subset of elements (nodes, arcs, paths, cliques, etc.) whose deletion minimizes a connectivity measure over the induced network. This problem has attracted significant attention in recent years because of its applications in several fields such as telecommunications, social network analysis, and epidemic control. In this paper we examine the problem of detecting critical cliques (CCP). We first introduce a mathematical formulation for the CCP as an integer linear program. Additionally, we propose a two-stage decomposition strategy that first identifies a candidate clique partition and then uses this partition to reformulate and solve the problem as a generalized critical node problem (GCNP). To generate candidate clique partitions we test two heuristic approaches and solve the resulting (GCNP) using a commercial optimizer. We test our approach in a testbed of 13 instances ranging from 25 to 100 nodes.