Exact algorithms for the minimum cost vertex blocker clique problem

Farzaneh Nasirian, Foad Mahdavi Pajouh, Josephine Namayanja

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)296-309
Number of pages14
JournalComputers and Operations Research
Volume103
DOIs
StatePublished - Mar 2019

Keywords

  • Combinatorial branch-and-bound
  • Interdiction
  • Lazy-fashioned branch-and-cut
  • Minimum cost vertex blocker clique problem

Fingerprint

Dive into the research topics of 'Exact algorithms for the minimum cost vertex blocker clique problem'. Together they form a unique fingerprint.

Cite this