Exact algorithms for the minimum cost vertex blocker clique problem

We study the minimum cost vertex blocker clique problem (CVCP), which is defined as follows. Given a simple undirected graph with weights and costs on its vertices and r > 0, detect a minimum cost subset of vertices to be removed such that the weight of any clique in the remaining graph is at most r. We propose a new characterization of the set of feasible solutions that results in new linear 0–1 programming formulations solved by lazy-fashioned branch-and-cut algorithms. A new set of facet-inducing inequalities for the convex hull of feasible solutions to CVCP are also identified. We also propose new combinatorial bounding schemes and employ them to develop the first combinatorial branch-and-bound algorithm for this problem. The computational performance of these exact algorithms is studied on a test-bed of randomly generated graphs, and real-life instances.