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 andr  0, detect a minimum cost subset of vertices to be removed such that the weight of any clique in the remaining graph is at mostr. 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.