Fabio Furini
email: fabio.furini@dauphine.fr

Ivana Ljubić
email: ivana.ljubic@essec.edu

Sébastien Martin
email: sebastien.martin@univ-lorraine.fr

Pablo San

The maximum clique interdiction problem

Keywords: Combinatorial Optimization, Interdiction Problems, Maximum Clique, (Social) Network Analysis, Most Vital Vertices

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1. Introduction 1

Corresponding author

Decision makers are often faced with the question of identifying the most vital (also called most vulnerable or most critical ) part of a network, which corresponds to a subset of vertices (or edges) of limited size, whose malfunctioning prevents the functionality of the network as a whole. Depending on the crucial property that needs to be maintained (or achieved) in the network, different vertices may be perceived as the most important ones. In some applications, we are looking for the most influential vertices (when it comes to spreading information in the network, see, e.g. [START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF]). In other applications, we might ask for the most critical vertices that may affect or destroy connectivity of the network, see, e.g. [START_REF] Furini | On integer and bilevel formulations for the k-vertex cut problem[END_REF][START_REF] Lalou | The critical node detection problem in networks: A survey[END_REF].

In this work we are concerned with the cohesiveness property of a (social) network. Within a network, there exist groups of individuals who interact with each other to such an extent that they could be perceived as separate entities. Such "tightly knit" groups are frequently identified using the notion of a clique, i.e., a subset of vertices that are pairwise connected. Networks with large cliques are considered cohesive, as the cliques model the archetypal structural pattern of the cohesion idea [START_REF] Moody | Clustering and Cohesion in Networks: Concepts and Measures[END_REF][START_REF] Moody | Structural cohesion and embeddedness: A hierarchical concept of social groups[END_REF]. The Maximum Clique Problem in a graph G = (V, E) (or a network) is a well-studied problem in Graph Theory and Operations Research. Its solution characterizes one of the most essential graph properties known as the clique number ω(G) of a graph, i.e., the size of a maximum clique in G. The clique number is also used as one of the measures of cohesiveness of a network [START_REF] Borgatti | Analyzing Social Networks[END_REF].

In this article, we study the problem of identifying a most vital subset of vertices with respect to the clique number, which is formally defined as follows: Given a graph G and an interdiction budget k ≥ 1, the Maximum Clique Interdiction Problem (CIP) asks to find a subset of at most k vertices to remove from G so that the clique number in the remaining graph is minimized. The set of interdicted vertices is called an optimal interdiction strategy, or equivalently, a set of the most vital vertices of the graph with respect to the clique number.

In the context of crime detection and prevention, large cliques have been identified as potential origins of catastrophic events such as terrorist or hacker attacks [START_REF] Berry | Emergent Clique Formation in Terrorist Recruitment[END_REF][START_REF] Sageman | Understanding Terrorist Networks[END_REF], as well as sources of outbreaks of sexually transmitted diseases [START_REF] Rothenberg | Personal risk taking and the spread of disease: Beyond core groups[END_REF]. In the analysis of terrorist networks [see, e.g., [START_REF] Chen | Crime data mining: A general framework and some examples[END_REF][START_REF] Sampson | Community structure and crime: Testing socialdisorganization theory[END_REF], cliques are used to model communities due to their ability to encode the interactions of groups of individuals who are all close friends with one another. Sageman [START_REF] Sageman | Understanding Terrorist Networks[END_REF] argues that cliques commonly produce social cohesion and a collective identity due to the interactions that foster solidarity and trust. Large cliques in a terrorist or crime network are capable of designing sophisticated large-scale operations like those of the 9/11 attacks, the series of coordinated terrorist attacks in Paris in 2014 and 2015, and numerous devastating coordinated attacks throughout Europe, Middle East, Africa and Asia, see [START_REF][END_REF] for a detailed map on recent attacks. More recents examples of security games in terrorist networks can be found e.g., in [START_REF] Guo | Coalitional security games[END_REF][START_REF] Wang | Computing optimal monitoring strategy for detecting terrorist plots[END_REF]. Hence, the cohesiveness of a terrorist/criminal network is one of its important features that needs to be carefully monitored and potentially reduced.

Applications of the CIP can also be found in other areas. For example, in modern telecommunication networks, Service Functions (SFs) such as firewalls, deep packet inspections (DPIs), web proxies, media gateways, etc. are used as middleboxes on the Service Provider Networks. Network Function Virtualization permits to virtualize the SFs so that using Software Defined Networks (SDNs), SFs can be disassociated from the physical elements of the network and installed as a software. This allows for a centralized control of network resources in which a centralized controller has visibility over the entire network, and has a complete view of the network topology [START_REF] Kim | Improving network management with software defined networking[END_REF]. An optimal CIP strategy in an SDN network identifies a set of vertices where SFs have to be installed so as to monitor and prevent suspicious activities while keeping the size of the remaining non-monitored cliques as small as possible.

In Figure 1, we provide a synthetic example graph of 12 vertices. In this graph, the clique number is 4 and there are four maximum cliques, i.e., K 1 = {v 1 , v 2 , v 3 , v 4 }, K 2 = {v 8 , v 9 , v 10 , v 11 }, K 3 = {v 1 , v 3 , v 4 , v 5 } and K 4 = {v 6 , v 8 , v 9 , v 11 }. If the interdiction budget k is equal to 2, an optimal interdiction strategy is shown in Figure 2. This strategy suggests that the pair of vertices depicted in black is critical for maintaining the cohesiveness of the graph. After removing vertices {v 4 , v 11 }, the clique number becomes 3 and there are six maximum cliques, e.g., {v 8 , v 9 , v 10 } or {v 6 , v 8 , v 9 }. It is important to notice that the interdiction strategy is often not unique. For instance, there are 3 • 3 optimal interdiction strategies obtained by choosing one vertex from the set {v 1 , v 3 , v 4 } and one vertex from the set {v 8 , v 9 , v 11 }. Furthermore, we can also observe in the graph of Figure 1 that the classical centrality measures (like degree, closeness, betweenness or eigenvector centrality) rank the vertices {v 5 , v 6 } as the most central ones. These two vertices are not the most critical ones for cohesiveness (i.e., the vertices necessary to preserve the clique number of the graph). On the contrary, among the 9 optimal CIP strategies (for k = 2), none contains v 5 nor v 6 . The vertices identified as the most critical ones for the cohesiveness are instead the ones belonging to the intersection of the two maximum cliques K 2 and K 4 and to the intersection of the other two maximum cliques K 1 and K 3 .

The CIP under investigation belongs to a family of Interdiction Problems (see e.g., [START_REF] Fischetti | Interdiction games under monotonicity[END_REF][START_REF] Tang | A class of algorithms for mixed-integer bilevel min-max optimization[END_REF]) which are a special class of Bilevel Optimization Problems. The latter ask for a solution of a two-level optimization problem in which the first level decisions affect the second-level optimization problem. Bilevel optimization problems are also seen as two-player Stackelberg games in which decisions of the first-and second-level are commonly denoted as leader's, respectively follower's decisions (see, e.g. a recent survey on bilevel optimization in [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF]). In our setting, the leader first determines a subset of vertices V to be removed from the network using a limited interdiction budget. After that, the follower observes the set V and chooses a maximum clique in the remaining graph. Being able to anticipate the optimal follower's solution for each of the possible vertex-removal strategies, the goal of the leader is to choose a strategy V that results in the worst possible outcome for the follower. More precisely, the goal of the leader is to find a best vertex-removal strategy so that the size of the maximum clique on the remaining graph is minimized.

We refer the interested reader to [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF][START_REF] Lozano | A value-function-based exact approach for the bilevel mixed integer programming problem[END_REF] for the most recent exact approaches in bilevel combinatorial optimization. In the literature, different classical combinatorial optimization problems have been studied in the bilevel context. Some of the most prominent examples include studies in which the follower solves the knapsack problem, the shortest-path problem, or the maximum flow problem on an interdicted network [START_REF] Fischetti | Interdiction games under monotonicity[END_REF][START_REF] Ratliff | Finding the n most vital links in flow networks[END_REF][START_REF] Tang | A class of algorithms for mixed-integer bilevel min-max optimization[END_REF][START_REF] Wood | Bilevel Network Interdiction Models: Formulations and Solutions[END_REF][START_REF] Cormican | Stochastic network interdiction[END_REF]. Interdiction problems on networks have been widely studied in the stochastic setting as well, see, e.g., [START_REF] Song | Risk averse shortest path interdiction[END_REF]. Some relevant applications of interdiction problems include the firefighting problem [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF][START_REF] Baggio | Towards Optimal Approximations for Firefighting and Related Problems[END_REF][START_REF] García-Martínez | The firefighter problem: Empirical results on random graphs[END_REF], the control of infections in hospitals [START_REF] Assimakopoulos | A network interdiction model for hospital infection control[END_REF], the allocation of protective resources in shortest-path networks [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF], the protection and analysis of supply chain disruptions [START_REF] Snyder | OR/MS models for supply chain disruptions: a review[END_REF], or the detection of drug smuggling [START_REF] Washburn | Two-person zero-sum games for network interdiction[END_REF]. Finally, knapsack interdiction problems are studied in [START_REF] Fischetti | Interdiction games under monotonicity[END_REF][START_REF] Caprara | Bilevel knapsack with interdiction constraints[END_REF].

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12
K 2 = {v 8 , v 9 , v 10 , v 11 }. v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11 v 12
Article Contribution. To the best of our knowledge, this article provides the first comprehensive theoretical and computational study on how to find the k most vital vertices of a graph with respect to its clique number. We provide a computationally efficient framework for solving the problem in large-scale realistic networks. The overall framework is constructed using building blocks that are derived from both, theoretical and algorithmic results. These results can be summarized as follows:

• The decision version of the CIP is Σ P 2 -complete (see Rutenburg [START_REF] Rutenburg | Complexity classification of truth maintenance systems[END_REF][START_REF] Rutenburg | Propositional truth maintenance systems: Classification and complexity analysis[END_REF], Ko and Lin [START_REF] Ko | On the Complexity of Min-Max Optimization Problems and their Approximation[END_REF]), but for a special class of graphs being a union of disjoint cliques, we show that the CIP can be solved in polynomial time. We also provide a closed formula for calculating the optimal solution for this special case.

• The latter result is then exploited for deriving a tight combinatorial lower bound min for solving the problem on general graphs.

• We provide conditions under which redundant vertices can be removed from the graph.

For the efficient reduction of the input graph, we show that the tight value of min plays a crucial role.

• Starting from a Bilevel Integer Programming model, we then derive a single-level reformulation based on an exponential family of Clique-Interdiction Cuts.

• We provide necessary and sufficient conditions under which clique-interdiction cuts are facet defining and we propose a fast lifting procedure.

• For the separation of clique-interdiction cuts, we develop a specially tailored combinatorial algorithm derived from one of the state-of-the-art approaches for finding maximum cliques in interdicted graphs.

• We also derive a battery of heuristic algorithms, to obtain high-quality incumbent solutions.

• All the above ingredients are combined in a computational framework which starts by calculating min and reducing the size of the input graph, before entering a branch-andcut phase (B&C) in which the efficient separation procedure and primal heuristics are employed.

In an extensive computational study, we demonstrate the effectiveness of all the components of our exact solution framework. The study is based on publicly available benchmark instances from various sources, including large-scale graphs representing real-world (social) networks with up to one hundred thousand vertices and three million edges. Most of these instances are solved to provable optimality within a short computing time, thus significantly outperforming the state-of-the-art generic bilevel mixed integer programming solver of Fischetti et al. [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF].

Our new approach is a powerful tool for analyzing and assessing the graph resilience against clique-interdiction attacks, i.e., the capacity of the graph of preserving a large clique (and also its cohesiveness). For different classes of input graphs, we analyze the evolution of the clique number as a function of the interdiction budget k. Our analysis reveals that social networks are "vulnerable" to clique-interdiction attacks as their clique number can be easily reduced by a large factor using a relatively low interdiction budget.

Finally, we point out that our exact solution framework can be extended to a more generic interdiction problem in which the follower solves a relaxed clique problem with hereditary property, such as s-plex, s-bundle, or s-defective clique (see [START_REF] Pattillo | On clique relaxation models in network analysis[END_REF] for a survey on clique relaxations).

The remainder of the paper is organized as follows: Section 2 concerns the literature review and Section 3 provides the bilevel integer programming formulation and complexity results.

In Section 4, we provide theory and methodology behind our combinatorial lower bound and the associated reduction procedure. The single-level reformulation along with the polyhedral study is given in Section 5. The separation procedure is described in Section 6. Computational results are provided in Section 7, and concluding remarks are given in Section 8.

Related Literature

To the best of our knowledge, and despite its relevance for analyzing the cohesiveness of networks, the CIP is a new problem that has not been studied in the previous literature. There are only three problems directly related to the CIP that we are aware of. The first one is the Minimum Vertex Blocker Clique Problem, in which one searches for a subset of vertices of minimum cardinality to be removed from a graph G, so that the maximum (weighted) clique in the remaining graph is bounded from above by a given integer r ≥ 1. This problem has been studied in Mahdavi Pajouh et al. [START_REF] Mahdavi Pajouh | Minimum vertex blocker clique problem[END_REF], where an exact algorithm based on row-generation has been proposed. In a computational study conducted on randomly generated graphs, the authors report optimal solution values for sparse graphs with 100 and 200 vertices, whereas most of the instances with density 0.5 or above remain unsolved.

The second related problem is the Edge Interdiction Clique Problem which has been introduced in Tang et al. [START_REF] Tang | A class of algorithms for mixed-integer bilevel min-max optimization[END_REF] and used as a case study for a generic exact approach for (the more general class of) interdiction problems. In the edge interdiction clique problem, the leader interdicts edges instead of vertices, and therefore the majority of results derived in this article are not directly applicable to this problem. Nevertheless, it is worth mentioning that the largest graphs considered in the computational study of Tang et al. [START_REF] Tang | A class of algorithms for mixed-integer bilevel min-max optimization[END_REF] contain 15 vertices, and most of them remained unsolved within an hour of computing time. Optimal solutions for these instances have recently been provided by the state-of-the-art exact solver for bilevel mixed integer programs of Fischetti et al. [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF].

We also mention the recent work of [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF], where the authors introduce the problem of finding the most vital vertices with respect to the maximum independent set. This problem is closely related to CIP, as finding a maximum independent set on a graph is equivalent to finding a maximum clique on the complement graph. The authors of [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF] provide some complexity results by showing that their problem is polynomial-time solvable on unweighted bipartite graphs, on cographs and graphs with bounded treewidth.

Finally, CIP also belongs to a larger family of Interdiction Games under Monotonicity, which has been recently addressed in Fischetti et al. [START_REF] Fischetti | Interdiction games under monotonicity[END_REF]. In this setting, the leader has a limited interdiction budget for deleting a subset of items, whereas the follower solves a maximization problem using the remaining items. The follower's subproblem is assumed to satisfy a monotonicity property, which is then exploited for deriving a single-level integer linear programming reformulation. The authors also study several strengthening inequalities which are of particular relevance for knapsack interdiction games. A computational study conducted on (multidimensional) knapsack interdiction games shows that this new approach significantly outperforms the previous state-of-the-art algorithm from [START_REF] Caprara | Bilevel knapsack with interdiction constraints[END_REF].

Bilevel formulation and problem complexity

In this section we first introduce the notation used in this article, we then provide a Bilevel Integer Linear Programming (ILP) formulation, after which we study the problem complexity.

Notation and definitions

Let G = (V, E) be a simple undirected graph with |V | = n and |E| = m. The complement of G is denoted G = (V, E), so E = {uv : uv / ∈ E}. Given a vertex set S, the subgraph of G induced by S is denoted by G[S]. We say that u and v are neighbours if there is an edge uv ∈ E. Neighbors of a vertex v are denoted by N (v). A subset S ⊆ V of vertices is a clique of G, if any two vertices of S are neighbours, and it is a stable set of G if it is a clique in G. The cardinality of the largest clique of G is denoted by ω(G), and the cardinality of the largest stable set by α(G). The maximum clique problem (MCP) in G is to find a clique of maximum size.

Given a vertex v ∈ V , the clique number of v, denoted by ω G (v) in the following, is the size of the largest clique v is contained in. The κ-core of a graph G is a maximal subgraph in which all vertices have degree at least κ. The coreness-number of a vertex v, denoted by coreness(v) in the following, is equal to κ if v belongs to a κ-core but not to any (κ + 1)-core. Obviously, the following inequality holds:

ω G (v) ≤ coreness(v) + 1 ≤ |N (v)| + 1 v ∈ V. (1)
For sparse graphs, the coreness-number of a vertex is often used as a rough approximation of its clique number, as it can be computed in O(|E|) time for all vertices in G [for further details, see [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF][START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF]. The maximum core number of a graph, denoted by core(G) in the following, is the maximum of the core numbers of the vertices of G. So, we have

ω(G) ≤ core(G) + 1 ≤ max v∈V deg(v) + 1. (2)
A coloring C of G is a partition of V into p non-empty stable sets: C = {V 1 , . . . , V p }, where all vertices belonging to V i are colored with the same color i (i = 1, . . . , p). A graph property is called hereditary on vertex induced subgraphs if for any S ⊆ V we have that if the property holds on G[S], then it also holds on G[S ], for any S ⊂ S, S = ∅.

Let S be the maximal stable set in G, i.e., α(G) = | S|, hence ω(G) ≤ |V | -α(G). For a given interdiction budget k such that k ≥ |V | -α(G) (i.e., there is enough budget to interdict at least all the vertices except those forming the maximum stable set), the optimal CIP solution value is at most one. Hence, we discard this trivial case and without loss of generality, we assume in the remainder of the paper that k < |V | -α(G).

Bilevel ILP formulation

The following binary decision variables are needed to model the problem as a bilevel integer linear program:

w u = 1, if vertex u is interdicted by the leader, 0, otherwise u ∈ V x u = 1, if vertex u is used in the maximum clique of the follower, 0, otherwise u ∈ V
Let W be the set of all feasible interdiction policies of the leader, i.e.:

W = w ∈ {0, 1} n : u∈V w u ≤ k . (3)
Similarly, let K represent the set of incidence vectors of all cliques in the graph G, i.e.:

K = x ∈ {0, 1} n : x u + x v ≤ 1, uv ∈ E , (4)
where the constraints x u + x v ≤ 1 ensure that two vertices cannot be part of a clique if there is no edge connecting them. With a slight abuse of notation, we will use both notations K ∈ K and x ∈ K, where x is the incident vector of K. Given an interdiction strategy w * ∈ W, let V w * be the associated set of interdicted (deleted) vertices.

The CIP can be formulated as follows:

min w∈W max K∈K |K| - u∈K w u . (5)
In the objective function of (5) we express the min-max nature of the problem: the leader controls (with the variables w) the outer minimization problem by interdicting at most k vertices of the graph, while the inner problem consists of calculating the clique number in the graph induced after the removal of the interdicted vertices. We call this inner problem the follower's subproblem). Observe that for the follower, the size of each clique K in G reduces by the number of interdicted vertices from K, which follows from the hereditary property of the clique (i.e., every vertex-induced subgraph of K is a clique itself). Therefore, the value |K| -u∈K w u denotes the size of the clique K after applying the interdiction strategy defined by w ∈ W. Hence, the formulation [START_REF] Baggio | Towards Optimal Approximations for Firefighting and Related Problems[END_REF] states that the leader chooses a set of vertices to interdict, so that among all possible cliques K ∈ K, the size of the maximum remaining clique is the smallest possible.

The CIP can be equivalently stated as:

min w∈W max x∈K u∈V (1 -w u )x u (6)
Indeed, we can rewrite the objective function of the follower in (6) as u∈V (1 -w u )x u = |K| -u∈K w u x u . The latter sum corresponds to the objective function in [START_REF] Baggio | Towards Optimal Approximations for Firefighting and Related Problems[END_REF] if and only if w u x u = w u if u ∈ K and w u x u = 0, otherwise. The latter is always true, as the vector x encodes the clique K, and hence x u = 1 if u ∈ K, and x u = 0, otherwise. Finally, the CIP can also be reformulated as the following bilevel integer linear program:

min w∈W max x∈K u∈V x u : x u ≤ 1 -w u , u ∈ V . (7)
Indeed, given an interdiction strategy w * ∈ W, the optimal solution of the follower's subproblem [START_REF] Baggio | Towards Optimal Approximations for Firefighting and Related Problems[END_REF] and the optimal solution of the follower's subproblem [START_REF] Balasundaram | Clique relaxations in social network analysis: The maximum k-plex problem[END_REF] are the same. Inequalities x u ≤ 1 -w u (u ∈ V ) are the linking interdiction constraints, making sure that the follower cannot chose a vertex u if it has been interdicted by the leader. They ensure that for a given vector w * , the follower searches for the maximum clique in the support graph in which the vertices v such that w * v = 1 have been removed. The bilevel ILP formulation ( 7) can be solved by using a Benders-like decomposition approach (cf. Section 5).

Problem complexity

In the following, we address the complexity of the decision version of CIP (denoted by d-CIP), stated as "Is there an interdiction strategy such that the maximum clique in the interdicted graph is not greater than some given bound ? ". Obviously, d-CIP is most probably not in NP for the following reason: Given a subset of k vertices to remove and a value of , to test whether the resulting graph does not contain a clique of size requires answering the decision problem of the maximum clique problem, which is NP-complete. Rutenburg [START_REF] Rutenburg | Complexity classification of truth maintenance systems[END_REF][START_REF] Rutenburg | Propositional truth maintenance systems: Classification and complexity analysis[END_REF] proved a stronger result, namely that the d-CIP is complete for the complexity class Σ p 2 (see Garey and Johnson [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-completeness[END_REF], Chapter 7, or Papadimitriou [START_REF] Papadimitriou | Computational Complexity[END_REF], Chapter 17 for further details on Σ p 2 ). A slightly stronger complexity result is given in [START_REF] Ko | On the Complexity of Min-Max Optimization Problems and their Approximation[END_REF].

The CIP is solvable in polynomial time if G is a bipartite graph, or if it is a cograph, or if its complement graph Ḡ has a bounded treewidth. This result follows from the related study on the most vital vertices with respect to the maximum independent set given in [START_REF] Bazgan | The most vital nodes with respect to independent set and vertex cover[END_REF].

Proposition 1. Assume that the graph G = (K 1 , . . . , K p ) is a union of vertex-disjoint cliques K i (1 ≤ i ≤ p) which are given as part of the input and such that |K 1 | ≥ • • • ≥ |K p | holds.
The optimal solution value of the CIP can be found in O(p) time, and an optimal solution can be calculated in O(p + k) time.

Proof. Let Q q = (K 1 , ..., K q ) be the subgraph induced by the first q cliques of G, 1 ≤ q ≤ p. Let k(Q q ) denote the size of an optimal interdiction strategy necessary to reduce the size of all cliques in Q q to |K q | -1. One easily verifies that this number can be computed as:

k(Q q ) = q + q-1 i=1 i • (|K i | -|K i+1 |).
In the following we must consider two cases:

k(Q p ) > k:
In order to compute the optimal solution value, it is then sufficient to find the value q * and the associated subgraph

Q q * such that k(Q q * ) > k and k(Q q * -1 ) ≤ k.
In that case, the optimal solution value is obtained as:

OPT(G, k) = max |K q * |, |K q * -1 | -1 - k -k(Q q * -1 ) q * -1 . ( 8
)
By definition, k(Q q * -1 ) is the budget necessary to interdict all cliques in Q q * -1 of size |K q * -1 | or more, so that the largest clique will be of size

|K q * -1 | -1. Then, the value k-k(Q q * -1 ) q * -1
provides the number of units by which the size of the largest clique in Q q * -1 can be further reduced using the remaining budget of k -k(Q q * -1 ). Finally, if

|K q * | > |K q * -1 | -1 - k-k(Q q * -1 ) q * -1
, the optimal solution value will be |K q * |. Finding the value of q * can be done in O(p) iterations, and each iteration has a constant time complexity, given the clique sizes.

k(Q p ) ≤ k: Using the same arguments, we can deduce OPT(G, k) = |K p | -1 - k -k(Q p ) p . (9)
To obtain an optimal solution, one has to (randomly) select

|K i | -OPT(G, k) vertices from each of the cliques K i (1 ≤ i ≤ q *
). This can be done in O(k + p) time.

In order to see how to compute OPT(G, k) using the formula [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF], consider a graph G composed by four cliques (p = 4) of size 10, 8, 5 and 5. Then, k(Q p ) = 12 and this corresponds to the budget k necessary to interdict all cliques of size 5 or more. Consider now a budget of k = 7, so we have k(Q 2 ) = 4 and k(Q 3 ) = 11, hence q * = 3. The value of OPT(G, 7) is given as max{5, 6}, where 6 represents the size of the maximum clique after interdicting 7 vertices in the first two largest cliques. Consider now a budget of k = 11, in this case q * = 4. The second term in formula ( 8) provides us the value of 4, as the size of the largest clique in Q 3 after interdicting 11 vertices from the three largest cliques, whereas the size of the fourth clique provides the optimal solution value of 5 (as there is not sufficient budget to reduce its size).

Proposition 1 provides the optimal CIP solution value for the graphs composed by unions of cliques, but it is particularly important for deriving a tight globally valid lower bound in the most general case, without imposing any restrictions on G (cf. Section 4).

Combinatorial bounds, tighter gaps and preprocessing

We propose combinatorial algorithms for calculating tight global lower and upper bounds.

Besides being useful for exact branch-and-bound-based approaches, we also demonstrate how these tight bounds help in reducing the size of the input graph. Let in the following min , max denote the global lower and upper bound on the solution value, and let opt be the optimal solution value (i.e., the size of the maximum clique after applying an optimal interdiction strategy).

Computing the global lower bound min

In Section 3, we have shown that if graph G is composed by union of disjoint cliques, the problem is polynomial-time solvable. We now exploit this result to derive a combinatorial lower bound, which is obtained by removing edges from G. The following result allows us to compute a global lower bound on the CIP value.

Proposition 2. Given a subgraph G = (V, E ) with E ⊂ E, an optimal CIP solution on G provides a valid lower bound for the optimal CIP solution on G.

Proof. Observe that ω(G ) ≤ ω(G). Let w ∈ W be a feasible interdiction strategy for G and let V w be the associated subset of interdicted vertices. The optimal CIP value on G is equal to min

w∈W ω(G[V \ V w ]).
Let w ∈ W be an optimal interdiction strategy on G. Then we have

ω(G [V \ V w]) ≤ ω(G[V \ V w]) = min w∈W ω(G[V \ V w ]).
Since the most left expression corresponds to a feasible CIP solution on G , and an optimal one is obtained by minimizing over all w ∈ W, the result follows immediately.

The result of Proposition 2 is rather counter-intuitive, as it states that by reducing the input graph, instead of obtaining a valid upper bound for a minimization problem, we obtain a valid lower bound. The key issue here is that we are in fact not reducing the feasibility space of the leader (as the set of vertices in G remains the same as in G), but only the feasibility space of the follower (which is reduced from all cliques induced by E to all cliques induced by E ). Observe, furthermore, that in terms of the problem complexity, the result of Proposition 2 does not help us much in solving the problem, since we still have to solve the same CIP problem, only on a smaller graph. However, this result can be particularly useful for special classes of graphs on which solving the CIP on G is easier than on G. This is exploited by the following result, where the proof for correctness of formula [START_REF] Berry | Emergent Clique Formation in Terrorist Recruitment[END_REF] follows from the proof of Proposition 1.

Corollary 1. Given a set Q p+1 = (K 1 , . . . , K p+1 ) of vertex-disjoint cliques of G, such that |K 1 | ≥ • • • ≥ |K p+1 |
, a valid lower bound min for the CIP can be obtained by computing

min =    max |K p+1 |, |K p | -1 -k-k(Qp) p , if k < k(Q p+1 ) |K p+1 | -1 -k-k(Q p+1 ) p+1 , otherwise (10)
The quality of this lower bound depends on the number of cliques p + 1 and their sizes (see Section 7 for the discussion on the empirical quality of the bounds and further implementation details).

Reducing the input graph

We start by describing another important solution property that is exploited in our study. Given a clique K and an interdiction strategy w * ∈ W, we say that K is covered by V w * if and only if at least one vertex from K is interdicted by w * , i.e., iff K ∩ V w * = ∅.

Property 1. If there exists a feasible interdiction strategy w * ∈ W, such that all cliques of size max + 1 in G are covered by V w * and there exists at least one clique K * in G, |K * | = max which is not covered by V w * , then max is a valid (non-trivial) upper bound on the CIP.

The latter property suggests another way of seeing the CIP: find a feasible interdiction strategy that minimizes the value of max while making sure all cliques of size max + 1 are covered.

We say that an interdiction strategy w ∈ W is minimal, if for the associated set of interdicted vertices V w , we have:

ω(G[V \ V w ]) < ω(G[(V \ V w ) ∪ {v}]), ∀v ∈ V w .
The following result identifies redundant vertices in the input graph G.

Proposition 3. Let v be an arbitrary vertex from V . If ω G (v) ≤ opt , then v cannot be part of a minimal optimal interdiction strategy.

Proof. By contradiction, assume that there exists a minimal optimal interdiction strategy w * ∈ W such that w * v = 1. We now construct a new feasible interdiction strategy w ∈ W as follows: wu := w * u for all u ∈ V, u = v and wv := 0. It remains to show that

ω(G[V \ V w]) = ω(G[V \ V w * ]) = opt .
Clearly, ω(G[V \ V w]) ≥ opt , since w is a feasible interdiction strategy. By Property 1, an optimal solution V w * must cover all cliques of size ≥ opt + 1. Since the largest cliques containing v are of size ≤ opt , then also the set V w = V w * \ {v} covers all the cliques of size

≥ opt + 1, which implies that ω(G[V \ V w]
) ≤ opt and this concludes the proof.

Hence, by focusing on the minimal interdiction policies, which can be done without loss of generality, one can preprocess the graph G and remove redundant vertices from it. To properly exploit Proposition 3, instead of using the (unknown) value of opt for removing the redundant vertices, one can employ a tight lower bound min . The following result gives a connection between the optimal solution value and the solution value found on the preprocessed graph from which redundant vertices are removed. Furthermore, an optimal interdiction strategy w on G, is also optimal for G.

Proof. Let w be an optimal interdiction strategy found on G. To show that w is also optimal for G, we distinguish between the following two cases:

Observe that the latter result allows us not only to fix the binary decision variables w v to zero, but also to modify the input graph G by removing its vertices, resulting into a smaller input graph for solving the follower's subproblem. This reduction preserves optimality, since the removal of a vertex v ∈ V prep only reduces the size of maximal cliques K such that |K| ≤ min , which are never going to constitute an optimal follower's response to an optimal interdiction strategy.

In a standard implementation, one would start with an arbitrary vertex, and solve the MCP by fixing this vertex to one. If the size of the obtained clique K is smaller than min , vertex v is removed from G and the process is repeated for the remaining vertices. This procedure can be time consuming, as the maximum clique algorithm has to be called per each vertex.

To overcome this drawback, the degree of a vertex can be used instead, as a trivial upper bound on the clique number of a vertex v. However, according to inequality (1), a much more accurate bound is the coreness-number of a vertex. Hence, in our implementation, we pre-calculate the coreness-number for all vertices (in the initialization phase), and then remove all vertices v such that coreness(v) ≤ min .

Computing the global upper bound max

We have implemented several construction heuristics in order to calculate a tight upper bound max and to create a pool of initial feasible solutions that are later given to the MIP solver. In all heuristics, if a vertex has been fixed to zero (e.g., removed by the preprocessing described above), it is not considered as a candidate for being interdicted. Our heuristics work in a greedy fashion, based on four different criteria: vertices are interdicted one-by-one, until the interdiction budget is exhausted. The chosen criteria are as follows:

• Vertex-degree: At the beginning, the vertices are sorted in non-increasing order according to their degrees. We start by interdicting the vertices with the highest degree first, and we stop once the interdiction budged is exhausted.

• Updated vertex-degree: The major difference to the "vertex-degree" heuristic is in the fact that now we recompute the vertex degrees, each time a vertex is interdicted.

• Vertex-coreness-number: at the beginning, the vertices are sorted in non-decreasing order according to their coreness number. Intuition behind this approach is that a vertex with a high coreness value is likely to belong to large cliques and shall be interdicted first. As mentioned above, coreness(v) + 1 is a rough upper bound on the size ω G (v) of the maximum clique containing this vertex.

• Vertex-color-number: This heuristic exploits the well-known result that the size of any feasible coloring gives an upper bound on the clique number of a graph [START_REF] Balas | Finding a maximum clique in an arbitrary graph[END_REF]. We first apply the greedy sequential coloring heuristic based on independent sets, where color classes are obtained incrementally using bitmasks, see [START_REF] San Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF][START_REF] San Segundo | An improved bit parallel exact maximum clique algorithm[END_REF]. This procedure runs in O(|V | 2 ) in the worst case and returns a feasible coloring. We then assign a label (corresponding to the color number) to each vertex. In this sequential greedy coloring heuristic, the higher the color associated to a vertex, the higher are the chances that this vertex belongs to a large clique. Therefore, we interdict the vertices in the non-increasing order with respect to their color numbers. Notice that the reordering of vertices, based on their color number, once they have been interdicted, will not influence the color number. So, there is no need to reorder the vertices after partially interdicting them, as long as they are interdicted starting with the highest color number first. As it will be shown in our computational study, vertex-color-number provides a very robust measure that delivers excellent heuristic solutions for sparse social networks.

Single-level ILP reformulation

In this section we provide an ILP formulation of the problem in the natural space of leader decision variables w. In addition, we provide a facial study of the underlying polytope, discussing under which conditions the proposed inequalities are facet defining.

The following is a valid ILP formulation for CIP:

min θ (11)
θ

+ u∈K w u ≥ |K| K ∈ K (12)
u∈V

w u ≤ k (13)
w u ∈ {0, 1} u ∈ V. (14)
To see that the model is valid, observe that for every feasible interdiction strategy w ∈ W, the follower's problem boils down to max x∈K u∈V x u (1 -wu ). Hence, the problem can be restated so that the set of feasible solutions of the follower does not depend on the actions of the leader anymore. Consequently, one can enumerate all cliques in G and optimize over the set K. This is why the problem can be equivalently restated as

min w∈W θ : θ ≥ u∈V xu (1 -w u ), x ∈ K ,
where x represents an arbitrary incidence vector of a clique in G.

This single-level ILP formulation contains an exponential number of constraints of type ( 12) that we will refer to as Clique Interdiction (CI) cuts. These constraints are NP-hard to separate: for each vector w and the associated θ given by the current solution of the formulation ( 12) and ( 13) , checking if there exists a violated interdiction cut requires finding a maximum weighted clique on G with vertex-weights c u = 1 -wu for all u ∈ V .

In a branch-and-cut algorithm applied to the above ILP formulation, it is sufficient to separate integer infeasible points only (fractional points being cut off using standard branching and general cutting plane mechanisms embedded in modern MIP solvers). Whenever w is integer, the separation problem consists in solving the MCP in the support graph

G[V \ V w]. Let K be the maximum clique in G[V \ V w]: if | K| > θ
then a violated CI cut associated to K is found and added to the model. This separation procedure can be a potential bottleneck for using a branch-and-cut procedure, unless an efficient clique solver is used for the separation of CI cuts. We have therefore implemented a tailored separation algorithm based on recent state-of-the-art approaches for the MCP (see Section 6 for further details).

Valid inequalities and facial study

In the following, we study the polytope of the single-level CIP formulation ( 11)- [START_REF] Chen | Crime data mining: A general framework and some examples[END_REF]. We provide necessary and sufficient conditions under which the clique interdiction cuts [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] are facet defining and we discuss heuristic lifting procedures designed to strengthen these inequalities.

Given the graph G and the interdiction budget k, let P(G, k) denote the convex hull of feasible solutions of the CIP formulation ( 11)- [START_REF] Chen | Crime data mining: A general framework and some examples[END_REF], that is,

P(G, k) = conv w ∈ {0, 1} |V | , θ ≥ 0 : θ + u∈K w u ≥ |K|, K ∈ K, u∈V w u ≤ k .
Let (V , q) denote a CIP solution where θ = q and the inderdiction strategy is defined by V . Proposition 5. The polytope P(G, k) is full dimensional.

Proof. We will prove this result by contradiction. Suppose that P(G, k) is contained in a hyperplane defined by the linear equation u∈V α u w u + βθ = γ, where α ∈ R |V | , β ∈ R, (α, β) = 0, and γ ∈ R. We show that α = 0, β = 0 and thus P(G, k) cannot be included in this hyperplane.

Let v ∈ V be an arbitrary vertex of the graph G. The three solutions (

V 1 = ∅, |V |), (V v = {v}, |V | -1) and (V v = {v}, |V |) are valid for P(G, k). We deduce that, α Vv + β • |V | = α Vv + β • (|V | -1
) and thus β = 0. We also deduce that,

α V 1 + β • |V | = α Vv + β • |V |, this implies α v = 0 for all v ∈ V . Proposition 6. Let u ∈ V .
1. The trivial inequality w u ≤ 1 defines a facet of P(G, k) if and only if k ≥ 2.

2. The trivial inequality w u ≥ 0 defines a facet of P(G, k).

Proof.

1. Let u ∈ V . If k = 1 then the inequality (13) dominates the inequality w u ≤ 1. For k ≥ 2, consider the following |V | + 1 feasible solutions that belong to P(G, k) and satisfy the inequality w u ≤ 1 with equality:

(V 0 = {u}, |V |), (V 1 = {u}, |V | -1) and (V v = {u, v}, |V |) for all v ∈ V \ {u}.
Clearly, these solutions are affinely independent, which concludes the proof.

2. Consider the following |V | + 1 feasible solutions from P(G, k) that satisfy w u ≥ 0 with equality:

(V 0 = ∅, |V |), (V v = {v}, |V |) for all v ∈ V \ {u} and (V 1 = {v }, |V | -1)
for some v = u Clearly, these solutions are affinely independent, so w u ≥ 0 defines a facet.

Lemma 1. Let K ∈ K be an arbitrary clique in G. The associated clique interdiction inequality [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] does not induce a facet if:

Obvious.

Even though the value of opt is not known in advance, the above result is useful for the separation of clique interdiction cuts. The result states that the more promising inequalities (in terms of improving the quality of lower bounds) are those with |K| ≥ min , considering thereby the value of min as tight as possible. This is also in line with our preprocessing procedure that removes all vertices from G whose clique number is not greater than min . In addition, without loss of generality, in the remainder of this section we focus on maximal cliques only.

Lemma 2. Let K be a maximal clique and v ∈ K.

If

ω(G[V \ V ]) ≥ |K| -|V ∩ K| + 1 ∀V ⊆ V where v ∈ V and |V | ≤ k, (15)
then there exists α v ≤ 0 such that the associated clique interdiction cut (12) can be down-lifted to θ

+ u∈K\{v} w u + α v w v ≥ |K|.
Proof. Let K be a maximal clique and let v ∈ K. The inequality θ + u∈K w u ≥ |K| is valid. Using a lifting procedure, see [34, p. 261], the coefficient α v of w v can be calculated as

α v = |K| -min    θ + u∈K\{v} w u |(w, θ) ∈ P(G, k) and w v = 1    . ( 16
)
Recall that to any feasible interdiction strategy w, we can associate the set V ⊂ V , |V | ≤ k of vertices to be deleted from G. Hence the minimum value of the right hand side is equal to min

V {ω(G[V \ V ]) + |K ∩ V | -1}
where the latter minimum is calculated over all feasible interdiction policies V that contain v. According to our condition [START_REF] Cormican | Stochastic network interdiction[END_REF], the size of the maximum clique in the graph G[V \ V ] plus the number of interdicted vertices which are in K, including v, is greater or equal |K| + 1. Then, min{θ + u∈K\{v} w u |(w, θ) ∈ P(G, k) and w v = 1} ≥ |K| and therefore α v ≤ 0.

Corollary 2. Let K ⊂ V be a clique. If there exists v ∈ K satisfying (15) then the inequality (12) cannot define a facet.

Finally, the following Proposition provides necessary and sufficient conditions under which the CI cuts are facet defining. This is the major theoretical result of this section, which allows to characterize the strength of the ILP formulation upon which our solution framework is built.

Proposition 7. Let K ∈ K be a maximal clique. Inequality (12) associated with K defines a facet of P(G, k) if and only if

• |K| ≥ opt + 1 • for all v ∈ K, there exists a subset V ⊆ V such that v ∈ V , |V | ≤ k and ω(G[V \ V ]) + |V ∩ K| ≤ |K|.
Proof. (⇒) See Lemma 1 and Corollary 2.

(⇐) Let us denote by α w + β θ ≥ γ inequality (12) associated with K. Let αw + βθ ≥ γ be a facet containing an equality [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] such that {(w, θ) ∈ P(G, k) : α w + β θ = γ } ⊆ {(w, θ) ∈ P(G, k) : αw + βθ = γ}. We will show that α = ρα and β = ρβ for some ρ ∈ R.

Let us first consider a set V of vertices which is an optimal interdiction strategy such that V ∩ K = ∅. Observe that such a set must exist, given that the optimal solution value is opt and |K| ≥ opt + 1, so at least one vertex from K has to be interdicted. Let V = V \ K.

• We will first show that α v = 0 for all v ∈ V . Let v ∈ V . We consider the solution

(V 1 = V , |K|). This solution is feasible since ω(G[V \ V ]) = opt ≤ |K|. Consider a second solution (V 2 = V \{v}, |K|
). This solution is also feasible because by interdicting one vertex less from V , the size of the maximum clique in G[V \ (V \ {v})] is at most opt + 1 ≤ |K|. These two solutions satisfy [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] with the equality. We deduce

α V 1 + β • |K| = α V 2 + β • |K|. This implies α v = 0 for all v ∈ V . • We now show that α v = 0 for all v ∈ (V \ K) \ V . Let v ∈ (V \ K) \ V . Let us consider the solution (V 3 = V 2 ∪ {v}, |K|
). This solution is valid since we interdict an additional vertex compared to

V 2 , so ω(G[V \ (V 2 ∪ {v}]) ≤ ω(G[V \ V 2 ]) ≤ |K|.
Clearly this solution satisfies [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] with equality. We deduce α

V 1 + β • |K| = α V 3 + β • |K|. This implies α v = 0 for all v ∈ (V \ K) \ V .
Let v k ∈ K. By the hypothesis there exists a set V k of vertices which is a feasible interdiction strategy

(|V k | ≤ k) such that v k ∈ V k and ω(G[V \ V k ]) + |V k ∩ K| ≤ |K|. By the inequality (12) (θ + u∈K w u ≥ |K|) we deduce that ω(G[V \ V k ]) + |V k ∩ K| = |K|. Let V k = V k \ K. • We will show that β = α v k , for the given v k ∈ K. Consider two feasible solutions (V k , ω 0 = ω(G[V \ V k ])) and (V 1 = V k \ {v k }, ω 1 = ω(G[V \ V k ]
) + 1) -they both satisfy [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] with equality. This implies α

V k + β • ω 0 = α V 1 + β • ω 1 and thus α v k = β.
• Finally, we will show that α ṽ = α v k , for all ṽ ∈ K, ṽ = v k . Let ṽ ∈ K and let Ṽ be a feasible interdiction strategy such that ṽ ∈ Ṽ , and

ω(G[V \ Ṽ ]) + | Ṽ ∩ K| ≤ |K|. Let Ṽ = Ṽ \ K and V k = V k \ K. We consider (V 4 = V k ∪ {v k }, |K| -1) and
(V 5 = Ṽ ∪ {ṽ}, |K| -1) two valid solutions. Indeed, in the graph G[V \ V k ] there remains the clique K and if we interdict one vertex of K plus the vertices of V k then the biggest clique has a size at most |K| -1. The same argument holds for the solution (V 5 , |K| -1).

Hence we can deduce that these two solutions satisfy [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF] with equality. This implies

α V 4 + β • (|K| -1) = α V 5 + β • (|K| -1). Since α v = 0 for all v ∈ V \ K, it follows that α ṽ = α v k , for all ṽ, v k ∈ K.
To finish the proof, we set β = ρ and thus α = ρα and β = ρβ .

Heuristic lifting procedure

According to the proof of Lemma 2, down-lifting coefficients of a clique interdiction cut requires solving another optimization problem given by ( 16), which is again a CIP on a smaller instance. We can apply some heuristic ideas instead, by underestimating the lefthand-side and overestimating the right-hand-side of the condition [START_REF] Cormican | Stochastic network interdiction[END_REF].

Observe that the left-hand-side of this inequality can be calculated as:

opt (v) = min{θ|(w, θ) ∈ P(G, k) and w v = 1} which is the value of an optimal CIP solution, assuming vertex v is interdicted. The value of opt (v) can be underestimated by calculating min (v), which is the lower bound obtained using the formula provided in Corollary 1. However, a slight modification is needed, to ensure this bound is valid for the case vertex v is interdicted. To obtain the value of min (v), we first remove vertex v from G, and then we compute vertex-disjoint cliques Q p on the fly, and stop as soon as we find p * such that k(Q p * +1 ) > k -1 (as the vertex v already consumes one unit of the interdiction budget). Notice that the values min (v) need to be calculated only once in the initialization phase, and they remain valid through the whole branch-and-cut procedure.

The right-hand-side of the condition ( 15) is simply overestimated by |K| (knowing that v ∈ V ∩ K). This results in the following heuristic condition for down-lifting the coefficients of the clique-interdiction cuts that can be perfomed in a computationally efficient way. Proposition 8. Let K be a maximal clique and v ∈ K. Let LB be the lower bound in the current node of the branch-and-bound tree. If max{ min (v), LB -1} ≥ |K| then the down-lifted clique-interdiction cut

θ + u∈K,u =v w u ≥ |K| is valid.
Proof. The proof follows from the condition (15) which ensures that in that case α v , the coefficient next to v in a valid clique-interdiction constraint is such that α v ≤ 0. The lefthand-side of ( 15) is underestimated by max{ min (v), LB -1}. We have to subtract the value of 1 from LB, since we do not know if vertex v has been interdicted or not, when this bound is calculated. The right-hand-side of this condition is overestimated by |K|.

Observe that such down-lifted clique interdiction cuts are only locally valid, and the globally valid ones can be similarly obtained by considering a global lower bound LB g instead.

Solving the separation problem by tailoring a state-of-the-art clique solver

The separation problem requires solving the MCP in a number of induced subgraphs G[V \V w ], where V w is a feasible interdiction strategy. To solve each MCP exactly, we have designed a specific branch-and-bound (B&B) algorithm inspired by the ideas described in [START_REF] Li | On minimization of the number of branches in branchand-bound algorithms for the maximum clique problem[END_REF][START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF], using a compact bitstring representation both for vertex sets and the adjacency matrix of the input graph. This B&B, denoted by IMCQ in the following, is a purely combinatorial approach that exploits tight lower and upper bounds for the clique number, along with efficient branching rules.

Initialization. IMCQ starts with a preprocessing phase, where the vertices of the input graph are reordered, a feasible solution K 0 and a tight upper bound ub are calculated, and a branching candidate set B 0 is determined.

The vertex ordering is essential for the efficient use of cache memory for bitstring graph representations and for reducing the size of the search tree, see [START_REF] San Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF][START_REF] San Segundo | An improved bit parallel exact maximum clique algorithm[END_REF]. We distinguish between two different categories of input graphs: large-scale sparse graphs and small or middle-size (n < 5, 000) but dense graphs. In the remainder of the paper, these categories will be referred to as sparse and non-sparse. For sparse graphs, vertices are sorted according to non-decreasing coreness in a degeneracy ordering using the algorithm of Batagelj and Zaversnik [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF]. For non-sparse graphs, vertices are sorted according to their degrees, following the approach from, e.g., San Segundo et al. [START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF].

In the case of sparse graphs, we use the fixed upper bound ub = 1 + core(G) for all interdiction strategies, where core(G) is the core number of G. In the case of non-sparse graphs, ub = min{ω(G), 1 + core(G[V \ V w ]}. For computing an initial solution K 0 , we use a simple greedy heuristic (see San Segundo et al. [START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF]).

The last initialization step is to determine an initial branching set of vertices B 0 ⊂ V \ V w , which are the candidate vertices which may belong to a clique larger than |K 0 |. B 0 is then determined by all the vertices v ∈ V \ V w such that 1 + coreness(v) > |K 0 |, where coreness(v) is the maximum core number of any subgraph that contains v.

Branching. We now describe the key ideas used to determine the candidates for branching, which are applied at each node of the B&B procedure. Given an input graph G = (V, E) and an integer q (corresponding to a valid lower bound on the MCP on G), it is possible to partition V into two disjoint sets of vertices P and B = V \ P such that ω(G[P ]) ≤ q, so that an optimal MCP solution can be found by branching on the vertices from B only. Reducing the size of the set B is crucial for an efficient implementation of a B&B-based MCP solver, see e.g., [START_REF] Segundo | Relaxed approximate coloring in exact maximum clique search[END_REF][START_REF] San Segundo | Infra-chromatic bound for exact maximum clique search[END_REF][START_REF] San Segundo | Improved infra-chromatic bound for exact maximum clique search[END_REF][START_REF] Li | On minimization of the number of branches in branchand-bound algorithms for the maximum clique problem[END_REF]. Computing ω(G[P ]) can be computationally expensive, and for this reason, this value is often replaced by an upper bound.

For sparse graphs, this upper bound is provided by a feasible κ-coloring on G, see [START_REF] San Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF][START_REF] San Segundo | An improved bit parallel exact maximum clique algorithm[END_REF]. If κ is strictly greater than q, the branching set B is determined by the union of vertices in color classes with a color number higher than q; otherwise no branching candidates exist and the algorithm backtracks. For the non-sparse graphs, we further reduce such obtained set B by an additional infrachromatic bounding function, see [START_REF] San Segundo | Infra-chromatic bound for exact maximum clique search[END_REF][START_REF] Li | On minimization of the number of branches in branchand-bound algorithms for the maximum clique problem[END_REF]. This function takes as input the feasible κ-coloring on G and reduces the upper bound κ by one unit each time a subset I of independent sets of the coloring is found such that it cannot contain a clique of size |I|. Our current implementation is inspired by the MaxSAT-based infrachromatic function described in [START_REF] Li | On minimization of the number of branches in branchand-bound algorithms for the maximum clique problem[END_REF], and tailored for the bitstring representation of G.

The infrachromatic bounding function is applied incrementally at every search node as follows. The P and B sets are initially determined by the greedy κ-coloring. Then, for every vertex v ∈ B, the function is called to determine whether or not ω(G[P ∪ {v}]) ≤ q. Every time the condition holds, v is added to P and the enlarged set P = P ∪ {v} is taken as reference in future iterations. After all the vertices in B have been processed, IMCQ will branch on the (few) vertices remaining in B.

At the beginning,

G = G[V \ V w ],
and each time a vertex v ∈ B is selected for branching (i.e., for inclusion into a clique under construction), the graph G is reduced by removing the non-neighbor vertices of v. The value of q is then determined as the difference between the size of the incumbent clique, and the size of the clique under construction.

Computational results

The purpose of this computational study is threefold: (1) to compare the exact solution framework for CIP presented in this paper with the state-of-the-art method available for general bilevel and interdiction problems; (2) to assess the practical applicability and the limits of our framework on large-scale social networks, and (3) to use this framework to analyze the resilience of (social) networks with respect to vertex-interdiction attacks, i.e., the decrease of the size of the maximum clique as a function of the incremental interdiction budget levels k.

In the following we first summarize our exact solution framework, followed by the explanation of benchmark instances and a detailed computational study. All the experiments have been performed on a computer with a 3.40 Ghz 8-core Intel Core i7-3770 processor and 16Gb RAM, running a 64-bit Linux operating system. The source codes were compiled with gcc 4.8.4 and -O3 optimizations. We used CPLEX 12.7.0 and the CALLABLE LIBRARIES framework to implement our branch-and-cut algorithm. CPLEX was run in single-threaded mode and all CPLEX parameters were set to their default values.

The exact solution framework CLIQUE-INTER

Our exact solution framework is based on the CIP formulation ( 11)-( 14) of Section 5. It is a branch-and-cut procedure combined with a preprocessing and efficient combinatorial algorithms for the computation of lower and upper bounds, and for the separation procedure. The framework is called CLIQUE-INTER in the remainder of the paper. These are its main components:

(i) An effective separation procedure of the CI cuts [START_REF] Cappanera | Optimal allocation of protective resources in shortestpath networks[END_REF]: To this end we apply the specialized combinatorial B&B algorithm (IMCQ) described in Section 6. IMCQ is an enhancement of one of the state-of-the-art MCP algorithms of San Segundo et al. [START_REF] San Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF] capable of effectively solving the MCP once the vertices of an interdiction strategy have been removed from the graph G. In addition, sharper cuts are obtained by maximal cliques (see Lemma 1); for this reason, before adding each CI cut, we make the associated clique maximal, i.e., potentially enlarging it with vertices that have been interdicted.

(ii) Tight CIP upper and lower bounds ( min and max ): In order to initialize the lower bound value of the variable θ of formulation ( 11)-( 14), we used the global lower bound min presented in Section 4.1. We create the subset Q p+1 required by Corollary 1 by iteratively extracting vertex-disjoint maximum cliques using IMCQ from G until we find the first p * such that k(Q p * +1 ) > k. In this way we minimize the number of times the NP-hard maximum clique problem is solved. On the other hand, by focusing on maximum (rather than random cliques), we preserve the quality of the bound min in a greedy fashion. By construction, the generated cliques are sorted in non-increasing order by their size, as required by the formula [START_REF] Berry | Emergent Clique Formation in Terrorist Recruitment[END_REF].

The cliques from the set Q p * +1 are also used to create an initial pool of CI cuts. In order to define a high-quality feasible CIP solution of value max to initialize formulation ( 11)-( 14), we apply a battery of sequential greedy heuristics presented in Section 4.3. If it turns out that min = max , the instance is solved to optimality, before even starting the B&C procedure.

(iii) The graph reduction: For large-scale real-world graphs, formulation ( 11)-( 14) becomes easily intractable, unless the input graph can be safely reduced to a smaller one. The reduction technique presented in Section 4.2, which exploits the tight lower bound min and preserves the optimality of the solution, is applied before calculating an initial upper bound max and entering the B&C phase.

As later shown in this computational section, all three components are crucial and necessary to guarantee an efficient computational performance of CLIQUE-INTER.

Test-bed of instances

In order to asses the performance of the newly proposed exact algorithm CLIQUE-INTER, we consider three sets of benchmarks instances, called Set A, Set B and Set C : Set C -Real-world networks. These instances have been taken from the [START_REF]10th DIMACS Implementation Challenge -Graph Partitioning and Graph Clustering[END_REF] and SNAP database. We consider instances with up to ≈ 100, 000 vertices and ≈ 3, 200, 000 edges. The reported 30 networks all fall into one of the following categories:

• Social Networks (with vertices representing individuals) such as: Interaction networks, where the edges refer to interaction via message posts, for example e-mail, as in iaemail-EU ; Recommendation networks, where the edges indicate communication in terms of a recommendation or an opinion (e.g., rec-eachmovie related to movie opinions); Collaboration networks, where edges represent scientific or other type of collaborations (e.g., astro-ph refers to preprints in the astrophysics archive, and cond-mat- * refer to the condensed matter archive www.arxiv.com). In some other social networks, edges refer to relationships of different types, such as friendship (e.g. Facebook, socfb), who-trusts-whom network (Soc-epinioins1 ), bloggers-interactions (soc-BlogCatalog), etc.

• Technological networks: In this case vertices are routers and edges represent communications between them, as in tech-internet-as.

• Scientific computing networks: These networks are meshes that are derived from mathematical analysis in different fields of science, i.e. finite elements (fe- * ), and other types (sc- * etc.).

Computational performance on random graphs of different size and densities

The purpose of this section is to demonstrate the effectiveness of the main components of CLIQUE-INTER and to determine the relative impact on the computational difficulty of the three main instance features, i.e., the number of vertices of a graph (|V |), the edge density of a graph (µ =

2|E| |V |•(|V |-1)
) and the amount of available interdiction budget (k). To this end, we use 220 random instances of Set A and we set a time limit of 600 seconds of CPU time for each run.

Recall that CLIQUE-INTER is the default setting of our exact framework, fully exploiting all its components (see Section 7.1). We test four additional configurations of CLIQUE-INTER, removing some of its components and measuring their impact on the computational performance:

1. CLIQUE-INTER (no bounds): in this configuration, all the ingredients are turned on, except for the calculation of combinatorial upper and lower bounds ( min and max ).

2. CLIQUE-INTER (no maximality): in this configuration, all the ingredients are turned on, except that we did not make the cliques maximal before adding the corresponding CI cuts.

3. Basic CLIQUE-INTER with IMCQ: in this configuration all components are removed, except the use of IMCQ to separate CI cuts.

4. Basic CLIQUE-INTER with CPLEX: this configuration corresponds to the basic B&C approach in which CI cuts are separated using CPLEX as a black-box clique solver applied to the classical clique ILP formulation with constraints associated to non-neighbour vertices. This configuration corresponds to the general implementation for interdiction games under monotonicity as given in Fischetti et al. [START_REF] Fischetti | Interdiction games under monotonicity[END_REF].

In order to give a graphical representation of the relative performance of the different configurations of CLIQUE-INTER, we report a performance profile in Figure 3. For each instance, we compute a normalized time τ as the ratio of the computing time of the considered configuration over the minimum computing time for solving the instance to optimality. For each value of τ in the horizontal axis, the vertical axis reports the percentage of the instances for which the corresponding configuration spent at most τ times the computing time of the fastest configuration. The curves start from the percentage of instances in which the corresponding configuration is the fastest and at the right end of the chart, we can read the percentage of instances solved by a specific CLIQUE-INTER configuration. The best performances are graphically represented by the curves in the upper part of Figure 3 and the horizontal axis is represented in logarithmic scale.

Figure 3 clearly shows that each of the components is necessary to achieve the best computational performance. CLIQUE-INTER is the fastest for 40% of the instances and it manages to solve to proven optimality almost 90% of the instances of Set A. From the figure, we can also see that the impact of separating CI cuts using IMCQ is crucial. Disabling the improvements based on min and max and not inserting "maximal" CI cuts have a remarkable detrimental effect, which is why the basic CLIQUE-INTER with IMCQ has a very poor computational performance. The computation cost of min and max is not negligible. For this reason, for the very small instances which are easily solvable, removing this computation can be somehow beneficial; for the most difficult instances, however, the update of the lower and upper bounds is crucial. The effects of the graph reduction technique for Set A were rather moderate (so we do not report these results separately), however this technique turns out to be inevitable for large-scale real-world networks (cf. Table 3), which is why we have decided to keep it in the default CLIQUE-INTER setting.

We now discuss the impact on the CPU time of the instance features using the best configuration of CLIQUE-INTER. In Figures 4 and5, we report the box plots of the computational times grouping the instances by edge density (Figure 4) and by graph size (|V |) and by interdiction budget (k) (Figure 5). In these figures, we graphically represent the computing times (in logarithmic scale) through their quartiles; the lines extending vertically from the boxes indicate the variability outside the upper and lower quartiles. Finally the outliers are plotted as individual points. In the upper part of both figures, we report the number of instances solved to proven optimality (#OPT) for each group of instances with similar characteristics and the number of instances solved by preprocessing (#PREP), i.e., when min = max . In the latter case, an optimal solution is computed without tackling formulation (11)-( 14). The number of instances solved by preprocessing is a proxy of the quality of both the CIP upper and lower bounds proposed in this paper.

In Figure 4, we have 11 groups of 20 instances each. We can observe that the computational time increases with the edge density up to a density value of 0.9 and then it starts to decrease. All instances with up to density 0.3 can be solved to proven optimality within the given time limit of 600 seconds by CLIQUE-INTER. The hardest instances are the ones with density 0.8 and 0.9, where CLIQUE-INTER is able to solve 15 out of 20 instances in each group. Several instances with low density can be solved by preprocessing, e.g., 11 for density 0.1 and 5 for density 0.2. None of the instances of density 0.8 and 0.9 can be solved by preprocessing. All instances with up to density 0.3 can be solved with an average CPU time less than 0.1 seconds. For all the other density classes the average CPU times of the solvable instances do not outmatch 100 seconds, but some instances can take up to several hundreds seconds.

In Figure 5, we have 20 groups of 11 instances each. As expected, we can observe that the computational time increases according to the number of vertices (|V |). In addition, the computational time is also directly correlated with the level of interdiction budget (k). All the instances with 50 and 75 vertices can be solved to proven optimality, independently of k. The figure shows that more instances can be solved by preprocessing for low levels of interdiction budget, e. [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF] and our approach (CLIQUE-INTER).

CLIQUE-INTER BILEVEL

Comparison with a state-of-the-art bilevel solver

In Table 1, we compare the results of the state-of-the-art bilevel and interdiction game solver from [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF] (called BILEVEL) with our new approach CLIQUE-INTER. Each row corresponds to 44 instances of Set A grouped by the number of vertices |V | ∈ {50, 75, 100, 125, 150}. For this test we used the same time limit of 600 seconds for each run. For each of the two solvers, we report the following values: the number of solved instances per group (#solved), the average computing time in seconds for those instances that were solved to optimality, the average exit gap after the time limit is reached (considering only those instances which were not solved to optimality) and the average root gap (over all instances). The exit gap is calculated as exit gap = UB -LB , where UB refers to the global upper bound computed by the corresponding method, and LB refers to the global lower bound of the same method. In order to measure the quality of lower bounds at the root node of the B&C tree (denoted by LB r ), we compute them with respect to the best known solution (BKS) as root gap = BKS -LB r .

Table 1 demonstrates that our new approach greatly outperforms the general-purpose bilevel solver of [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF] by several orders of magnitude. All instances with 50 and 75 vertices are solved to optimality in less than 2 seconds on average by CLIQUE-INTER, whereas the bilevel solver manages to solve only 2/3 and 1/3 of the instances, respectively. Similar behavior can be observed for larger instances, where, for example, for graphs with 150 vertices the bilevel solver manages to solve only a single instance in more than 5 minutes, whereas we solve 70% of them, in less than 1/2 minute on average. These results can be easily explained by the quality of root bounds: whereas the average absolute gaps at the root node for our approach are between 0.16 and 1.4, those of BILEVEL range between 8.5 and 16.4. This has a strong impact on the size of the B&C tree. For example, for 28 instances of size 50 solved by both approaches, CLIQUE-INTER requires an average number of 1.5 B&C nodes, compared to 1960 nodes required by BILEVEL.

Performance of CLIQUE-INTER on DIMACS2 graphs and large real-world networks

In Table 2, we show the performance of CLIQUE-INTER on the dense graphs of Set B. All these instances have 200 vertices and the table reports their density (µ), the size of maximum cliques (ω(G)) and the CPU time necessary to compute it using IMCQ (time ω ). We test two levels of interdiction budget, i.e., k = 20 and k = 40. For these tests we set a time limit of 3600 seconds and T.L. is reported for the instances not solved to proven optimality. For each value of k, we report the value of the final lower and upper bounds (LB and UB), the total CPU time spent in solving formulation ( 11)-( 14) and the values of the initial lower and upper bounds ( min and max ). In case an instance is solved to proven optimality then LB=UB, in case an instance is solved during the preprocessing min = max . In this latter case, we do not report the CPU time since it is not necessary to tackle formulation ( 11)-( 14), and the time necessary to compute min and max is negligible. The time taken by IMCQ to find ω(G) for the instances of Set B is often negligible, except for sanr200 0.9 , where it takes 1.9 seconds. CLIQUE-INTER is able to solve 12 and 8 instances out of 14 instances, for k = 20 and k = 40, respectively. From the table, we can see that the gap between min and max is small for all instances except in a few cases, e.g., for san200 0.9 1 and san200 0.9 2 and k = 40 where the gap is 10 and 8, respectively. In most of the remaining instances the initial gap is less than 3, showing that also for this set of instances min and max provide good-quality lower and upper bounds. For k = 20, three instances can be solved to proven optimality by preprocessing alone and, for k = 40, two instances are solved by preprocessing. As already observed on the instance Set A, increasing the level of budget increases the computational difficulty as well.

In Table 3 14) is actually solved on a small fraction of vertices. This reduction is more effective for small values of interdiction budget k. Finally, the columns "cuts" and "nodes" reveal that the number of CI cuts separated and B&C nodes explored is often small. Only in some cases, several hundreds of cuts are separated using IMCQ and the number of explored nodes is typically smaller that 500. In some rare cases the number of explored nodes can be high, as in Slashdot0902, which requires 14105 nodes.

Clique-interdiction curve of a graph

We define the resilience of (social) networks with respect to clique-interdiction attacks as the relative decrease of the size of the maximum clique in function of the interdiction budget. This can also seen as the ability of the network to survive a clique-interdiction attack.

We plot the size of an optimal CIP solution (as a percentage of the size of a maximum clique on the original graph) for different values of the interdiction budget k. Figure 6 depicts this relation for two quite different types of networks: very sparse social networks (taken from the DIMACS10 data set) versus very dense graphs (taken from the DIMACS2 data set). On the x axis we plot the percentage of the total number vertices (representing the interdiction budget k). On the y axis, we provide the relative size of the optimal CIP solution compared to the value of ω(G). Not surprisingly, the obtained results indicate that significantly higher interdiction budget is needed for dense networks. With the interdiction budget of only 1% of vertices, one can reduce the size of the maximum clique between 40% and 95% in case of social networks (see astro-ph and memplus), whereas dense networks are much more resistant to this kind of attacks. With the 1% of interdiction budget, the size of the maximum clique can be reduced only by a few percent in most of the cases shown in Figure 6.

The obtained results, both in terms of CPU times and the size of networks that can be solved to optimality, indicate that our solver can be used as a powerful decision making tool for analyzing and assessing the network resilience against clique-interdiction attacks. Measuring the clique-interdiction number can provide to decision makers an important information about the structure of the network concerning its densely connected components. Our exact solver can also be used for simulation purposes, to find out which vertices need to be protected (in case of a clique-interdiction attack).

Extensions and conclusions

In this article we studied the interdiction problem in a network in which the leader chooses up to k vertices to delete, so as to minimize the clique number determined by the follower in the resulting network. We studied the problem complexity for special graphs, and we derived a single-level ILP formulation with an exponential number of constraints called cliqueinterdiction cuts. In a polyhedral study of the underlying polytope, we provided necessary and sufficient conditions for these cuts to be facet defining and we designed effective lifting procedures. The separation of these cuts required development of an efficient exact solver for the maximum clique problem, which we tailored for the clique interdiction problem. The deep understanding of the underlying problem allowed us to derive tight combinatorial lower and upper bounds, along with an efficient preprocessing phase for drastically reducing the problem size. Our framework is the first one being able to solve to proven optimality realworld large-scale (social) networks from various publicly available resources, thus, drastically outperforming the state-of-the-art general purpose bilevel solver from Fischetti et al. [START_REF] Fischetti | A new general-purpose algorithm for mixed-integer bilevel linear programs[END_REF]. This shows that significant improvements (in terms of the size of input networks and computing times) can be achieved by tailored exact algorithms for particular classes of interdiction problems. The code will be made available online (after the revision process is finished), to help decision makers analyze the resilience of networks to maintain a large clique after a clique-interdiction attack. Extensions. In some applications where the concept of clique may be too restrictive to define a community, clique-relaxations can be used instead, see [START_REF] Balasundaram | Clique relaxations in social network analysis: The maximum k-plex problem[END_REF][START_REF] Pattillo | On clique relaxation models in network analysis[END_REF]. Clique-relaxations are obtained by relaxing some of the clique defining properties, and our exact solution framework can be extended to the interdiction problems in which the follower solves the maximum relaxed clique problem, as long as the latter one satisfies the hereditary property. Relaxed cliques with hereditary properties are obtained by relaxing: the degree of the vertices (s-plex), the distance between the vertices (s-clique), the density of the edges (s-defective clique) and the connectivity between the vertices (s-bundle). Precise definition of these problems can be found in e.g., [START_REF] Pattillo | On clique relaxation models in network analysis[END_REF]. One can show that our single-level reformulation (and accordingly the branch-and-cut algorithm) can be extended for solving this class of interdiction problems. The key element of the B&C implementation would be an efficient exact solver for the maximum relaxed clique problem at hand. We point out however that the theory and methodology derived in this paper does not directly carry over to solving interdiction problem in which the follower maximizes a weighted hereditary problem on a network. These problems deserve a special attention and will be subject of our future studies.

Other interesting problem extensions concern the introduction of multiple leaders (that could act in a collaborative or competitive way), multiple followers, or both (see, e.g., [START_REF] Sinha | Finding optimal strategies in a multi-period multi-leader-follower Stackelberg game using an evolutionary algorithm[END_REF]). Similarly, a multi-period setting could be worthy of investigation, as well as allowing incomplete information (like, e.g., in Stackelberg security games, [START_REF] Guo | Coalitional security games[END_REF][START_REF] Lagos | A branch and price algorithm for a Stackelberg security game[END_REF]).

Finally, it would be interesting to combine other centrality measures with the clique number for measuring the cohesiveness of a network. That way, one could capture vertices which are the most vital ones with respect to different measures simultaneously (as for example in [START_REF] Rysz | Finding clique clusters with the highest betweenness centrality[END_REF], where the authors combine maximum cliques with the betweenness centrality). A very interesting line of research would be to take into consideration the cohesiveness of a network and, at same time, its connectivity. Studying the most vital vertices with respect to such new measures of cohesiveness would certainly provide some new and relevant insights for the analysis of (social) networks.

Figure 1 :

 1 Figure 1: An example graph G for the CIP. Before interdiction, the clique number is ω(G) = 4. One of the four maximum cliques is shown in grey, i.e., the clique K 2 = {v 8 , v 9 , v 10 , v 11 }.

Figure 2 :

 2 Figure 2: The vertices of an optimal interdiction strategy of the CIP with a budget k = 2 are shown in black, and one of the remaining maximum cliques of size 3 is shown in grey, i.e., the clique {v 6 , v 8 , v 9 }. Dashed lines represent the edges which are incident to the interdicted vertices, as they cannot be used to build cliques in G[V \ {v 4 , v 11 }].

Proposition 4 .

 4 Let V prep = {v ∈ V : ω G (v) ≤ min } be the set of vertices v satisfying the (weakened) property of Proposition 3. Let Ṽ = V \ V prep and G = G[ Ṽ ] and let ˜ opt denote the optimal CIP solution value on G. Then opt = max{ ˜ opt , min }.

  Set A -Random graphs. We created a set of 55 Erdős-Rényi random G(n, p) graphs of different sizes (n = |V | ∈ {50, 75, 100, 125, 150}) and edge densities (p ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.98}). We set k to four different percentages of |V |, i.e., k ∈ { 0.05• |V | , 0.1 • |V | , 0.2 • |V | , 0.4 • |V | }.In this way, we created the Set A of 220 instances.Set B -Synthetic graphs. This set contains 16 well known synthetic instances with |V | = 200 from the 2nd DIMACS challenge on Maximum Clique, Graph Coloring, and Satisfiability[START_REF]DIMACS2. 2nd DIMACS Implementation Challenge -NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability[END_REF]. Most of them are still employed as test-bed by state-of-the-art exact MCP algorithms.

  CLIQUE-INTER (no bounds) CLIQUE-INTER (no maximality) Basic CLIQUE-INTER with IMCQ Basic CLIQUE-INTER with CPLEX

Figure 3 :

 3 Figure 3: Performance profile of the different configurations of CLIQUE-INTER.

Figure 4 :

 4 Figure 4: The total CPU times on the random graphs of Set A, grouped by the edge density.

  g., for instances with 50 vertices, 7 instances can be solved by preprocessing when k = 0.05 • |V | and only 2 when k = 0.4 • |V | . All the instances with 50 vertices are solved in less than 1 second and all the instances with 75 vertices are solved in less than 100 seconds. All instances with low values of k (k = 0.05 • |V | and k = 0.1 • |V | ) can be solved to proven optimality in less than 1 and 100 seconds, respectively.

Figure 5 :

 5 Figure 5: The total CPU times on the random graphs of Set A, grouped by the network size and the interdiction budget.

Figure 6 :

 6 Figure 6: Clique-interdiction curves for social networks (up) and dense graphs (down).

1 .

 1 |K| ≤ opt , or 2. K is not maximal. Proof. 1. Observe that, by definition, we have θ ≥ opt . Hence, for |K| < opt the equality u∈K w u = |K| -θ has a negative right-hand side, i.e., there is no feasible solution satisfying this equation. On the other hand, for |K| = opt , the CI cut θ + u∈K w u = |K| is dominated by θ ≥ opt .

Table 1 :

 1 Comparison with state-of-the-art bilevel solver (BILEVEL) from

	| #	# solved time exit gap root gap	# solved	time exit gap root gap
	50 44	44 0.01	-	0.16	28 68.58	6.44	8.50
	75 44	44 1.45	-	0.41	14 120.19	9.47	10.91
	100 44	37 9.30	1.00	0.98	7 164.42	12.65	13.11
	125 44	35 13.43	1.33	1.20	2 135.33	13.88	14.73
	150 44	33 27.23	1.91	1.43	1 397.52	16.42	16.39

  , we show the performance of CLIQUE-INTER on the large real-world networks of Set C. As discussed in Section 7.2, this set is composed by 30 sparse graphs with up to 100K vertices and 3200K edges. The table reports for each instance the number of vertices (|V |), the number of edges (|E|), the size of maximum clique (ω(G)) and the CPU time necessary to compute it using IMCQ (time ω ). For these tests, we used a time limit of 3600 seconds for each run. Since these graphs are large, to test realistic levels of interdiction budget, we set CLIQUE-INTER k = 40 µ ω(G) time ω LB UB time min max LB UB time min max

	brock200 1	0.75	21	0.2 18 18 938.2 16 18 15 17 T.L. 13 17
	brock200 2	0.50	12	0.0	9	9	0.1	8 10	8	9 T.L.	7	9
	brock200 3	0.61	15	0.0 12 12	1.0 11 13 11 11 160.6	9 12
	brock200 4	0.66	17	0.0 14 14 2421.8 12 15 12 13 T.L. 10 13
	c-fat200-1	0.08	12	0.0 10 10	-10 10	9	9	-	9	9
	c-fat200-2	0.16	24	0.0 20 20	-20 20 18 18	-18 18
	c-fat200-5	0.43	58	0.0 52 52	0.0 51 52 46 46	0.0 44 46
	san200 0.7 1	0.70	30	0.0 17 17	5.4 16 18 15 15 134.4 14 17
	san200 0.7 2	0.70	18	0.0 14 14	16.7 13 15 12 12	5.6 11 15
	san200 0.9 1	0.90	70	0.0 50 50	-50 50 40 40	13.3 39 49
	san200 0.9 2	0.90	60	0.1 41 41	3.2 41 42 34 34 2266.9 33 41
	san200 0.9 3	0.90	44	0.0 33 34 T.L. 32 37 28 31 T.L. 26 34
	sanr200 0.7	0.70	18	0.1 15 15	29.2 14 16 13 14 T.L. 11 15
	sanr200 0.9	0.90	42	1.9 33 35 T.L. 31 35 28 32 T.L. 25 33
	gen200 p0.9 44 0.90	44	0.1 34 34 674.4 32 38 29 31 T.L. 26 36
	gen200 p0.9 55 0.90	55	0.1 38 38	62.4 37 41 32 33 T.L. 29 40

k = 0.005 • |V | and k = 0.01 • |V | . For this set of instances the time to compute min is not always negligible and we report it in the column time p . As explained in Section 4.1, min is computed starting from a set Q p = (C 1 , . . . , C p ) of p vertex-disjoint cliques of G and the CLIQUE-INTER k = 20

Table 2 :

 2 Computational results obtained by the CLIQUE-INTER on the instances with |V | = 200 from the 2nd DIMACS Challenge[START_REF]DIMACS2. 2nd DIMACS Implementation Challenge -NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability[END_REF]. minimum p, which provides the best min , is determined by the level of interdiction budget k.In the table, we only report the CPU time necessary to compute min for k = 0.01 • |V | , the time to compute min for the k = 0.001 • |V | is smaller. The table reports for each instance the optimal solution value (OP T * ) and, in case the time limit is reached, we report T.L. and OP T * is the best known UB. As for Table2, the total CPU time spent in solving formulation (11)-(14) is reported in the column "time". In the column |V prep |, we report the number of vertices that can be removed from the graph, as explained in Section 4.2. We report the value of the initial upper and lower bound min and max and the number of CI cuts separated and the number of B&C nodes explored solving formulation (11)-[START_REF] Chen | Crime data mining: A general framework and some examples[END_REF]. CLIQUE-INTER is able to solve to proven optimality 28 out of 30 instances for both levels of interdiction budget. In the preprocessing phase, 6 and 4 instances are solved for k = 0.005 • |V | and k = 0.01 • |V | , respectively. The gap between min and max is relatively small also for this set of instances, with a few exceptions, e.g, for socfb-UF and k = 0.01 • |V | the gap is 15 or for socfb-UIllinois and k = 0.01 • |V | the gap is 11. The graph reduction technique is crucial for these set of large instances. The table shows that huge reductions can be achieved, i.e., if we compare the size of the initial set of vertices |V | and the number of vertices that can be discarded |V prep |, we can see that formulation (11)-(

ω(G[ Ṽ \ V w]) < l min : In that case, w is a feasible interdiction strategy on G, with the follower's optimal response on the remaining graph with value min . This is due to the facts that: (i) all vertices from V prep cannot appear in a clique of size larger than min , (ii) min is a valid lower bound and thus there exist at least one clique of size min in the graph G[V \ V w]. Hence, min is equal to the optimal solution value opt .

ω(G[ Ṽ \ V w]) ≥ l min : In that case, ˜ opt = opt , due to the fact that interdicting any of the vertices from V prep will not result in a better interdiction strategy, because the largest clique that can be covered by interdicting vertices from V prep is of size min . This concludes the proof.

Acknowledgment

Valuable comments of four anonymous reviewers are highly appreciated. Ivana Ljubić is partially funded by the Vienna Science and Technology Fund (WWTF) through project ICT15-014. Pablo San Segundo is funded by the Spanish Ministry of Economy and Competitiveness (grants DPI 2014-53525-C3-1-R, DPI2017-86915-C3-3-R).