Given a vertex-weighted undirected graph with blocking costs of its vertices and edges, we seek a minimum cost subset of vertices and edges to block such that the weight of any γ-quasi-clique in the interdicted graph is at most some predefined threshold parameter. The value of [Formula: see text] specifies the edge density of cohesive vertex groups of interest in the network. The considered weighted γ-quasi-clique interdiction problem can be viewed as a natural generalization of several variations of the clique blocker problem previously studied in the literature. From the application perspective, this setting is primarily motivated by the problem of disrupting adversarial (“dark”) networks (e.g., social or communication networks), where γ-quasi-cliques represent “tightly knit” groups of adversaries that we aim to dismantle. We first address the theoretical computational complexity of the problem. We then exploit some basic characterization of its feasible solutions to derive a linear integer programming (IP) formulation. This linear IP model can be solved using a lazy-fashioned branch-and-cut scheme. We also propose a combinatorial branch-and-bound algorithm for solving this problem. The computational performance of the developed exact solution schemes is studied using a test bed of randomly generated and real-life networks. Finally, some interesting insights and observations are also provided using a well-known example of a terrorist network. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: The work of S. Butenko was partially supported by the Air Force Office of Scientific Research under Award FA9550-23-1-0300. The work of O. A. Prokopyev was partially supported by the Office of Naval Research under Award ONR N00014-22-1-2678. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0027 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0027 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . The online appendix is available at https://doi.org/10.1287/ijoc.2023.0027 .

We consider a two-player interdiction problem staged over a graph where the attacker’s objective is to minimize the cost of removing edges from the graph so that the defender’s objective, that is, the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level r. Standard approaches for graph interdiction frame this type of problems as bilevel formulations, which are commonly solved by replacing the inner problem by its dual to produce a single-level reformulation. In this paper, we study an alternative integer program derived directly from the attacker’s solution space and show that this formulation yields a stronger linear relaxation than the bilevel counterpart. Furthermore, we analyze the convex hull of the feasible solutions of the problem and identify several families of facet-defining inequalities that can be used to strengthen this integer program. We then proceed by introducing a different formulation defined by a set of so-called supervalid inequalities that may exclude feasible solutions, albeit solutions whose objective value is not better than that of an edge cut of minimum cost. We discuss several computational aspects required for an efficient implementation of the proposed approaches. Finally, we perform an extensive set of computational experiments to test the quality of these formulations, analyzing and comparing the benefits of each model, as well as identifying further enhancements. Summary of Contribution: Network interdiction has received significant attention over the last couple of decades, with a notable peak of interest in recent years. This paper provides an interesting balance between the theoretical and computational aspects of solving a challenging network interdiction problem via integer programming. We present several technical developments, including a detailed study of the problem's solution space, multiple formulations, and a polyhedral analysis of the convex hull of feasible solutions. We then analyze the results of an extensive set of computational experiments that were used to validate the effectiveness of the different methods we developed in this paper.

This article introduces the minimum spanning k-core problem that seeks to find a spanning subgraph with a minimum degree of at least k (also known as a k-core) that minimizes the total cost of the edges in the subgraph. The concept of k-cores was introduced in social network analysis to identify denser portions of a social network. We exploit the graph-theoretic properties of this model to introduce a new approach to survivable interhub network design via spanning k-cores; the model preserves connectivity and diameter under limited edge failures. The deterministic version of the problem is polynomial-time solvable due to its equivalence to generalized graph matching. We propose two conditional value-at-risk (CVaR) constrained optimization models to obtain risk-averse solutions for the minimum spanning k-core problem under probabilistic edge failures. We present polyhedral reformulations of the convex piecewise linear loss functions used in these models that enable Benders-like decomposition approaches. A decomposition and branch-and-cut approach is then developed to solve the scenario-based approximation of the CVaR-constrained minimum spanning k-core problem for the aforementioned loss functions. The computational performance of the algorithm is investigated via numerical experiments.

We study the minimum vertex blocker clique problem (VBCP),1 which is to remove a subset of vertices of minimum cardinality in a weighted undirected graph, such that the maximum weight of a clique in the remaining graph is bounded above by a given integer r ≥ 1. Cliques are among the most popular concepts used to model cohesive clusters in different graph‐based applications, such as social, biological, and communication networks. The general case of VBCP on weighted graphs is known to be NP‐hard, and we show that the special case on unweighted graphs is also NP‐hard for any fixed integer r ≥ 1. We present an analytical lower bound on the cardinality of an optimal solution to VBCP, as well as formulate VBCP as a linear 0–1 program with an exponential number of constraints. Facet‐inducing inequalities for the convex hull of feasible solutions to VBCP are also identified. Furthermore, we develop the first exact algorithm for solving VBCP, which solves the proposed formulation by using a row generation approach. Computational results obtained by utilizing this algorithm on a test‐bed of randomly generated instances are also provided. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 48–64 2014