  


The Maximum Clique Interdiction Game
Fabio Furini(fabio.furinidauphine.fr) Abstract: We study the two player zerosum Stackelberg game in which the leader interdicts (removes) a limited number of vertices from the graph, and the follower searches for the maximum clique in the interdicted graph. The goal of the leader is to derive an interdiction policy which will result in the worst possible outcome for the follower. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We design an exact solution framework based on a Bilevel Integer Linear Programming model. Thanks to the study of the polytope of the corresponding singlelevel reformulation, we derive a branchandcut algorithm and enhance it by tight combinatorial lower and upper bounds, which also allow for a drastic reduction of the size of the input graph. Our model is based on an exponential family of CliqueInterdiction Cuts whose separation requires solving the maximum clique problem. We derive an effective separation procedure based on a newly developed combinatorial algorithm that is tailored for finding maximum cliques in interdicted graphs. We assess the applicability and the limits of our exact framework on publicly available instances, including largescale social networks with up to one hundred thousand vertices and three million edges. Most of these instances are solved to provable optimality within short computing times. Our code (which will be also publicly available) allows to analyze the resilience of (social) networks with respect to vertexinterdiction attacks, i.e., the decrease of the size of the maximum clique in function of incremental interdiction budget level. Keywords: Network Interdiction, Maximum Clique, Social Network Analysis 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  