  


The Maximum Clique Interdiction Problem
Fabio Furini (fabio.furinidauphine.fr) Abstract: Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We propose an integer linear programming formulation of the problem based on an exponential family of CliqueInterdiction Cuts and we give necessary and sufficient conditions under which these cuts are facetdefining. Our new approach provides a useful tool for analyzing the resilience of (social) networks with respect to cliqueinterdiction attacks, i.e., the decrease of the size of the maximum clique as a function of an incremental interdiction budget level. On a benchmark set of publicly available instances, including largescale social networks with up to one hundred thousand vertices and three million edges, we show that most of them can be analyzed and solved to proven optimality within short computing time. Keywords: Network Interdiction, Maximum Clique, Social Network Analysis, Most Vital Vertices Category 1: Integer Programming Category 2: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [PDF] Entry Submitted: 01/16/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  