Minimum edge blocker dominating set problem

Foad Mahdavi Pajouh, Jose L. Walteros, Vladimir Boginski, Eduardo L. Pasiliao

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r > 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r > 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs.

Original languageEnglish
Pages (from-to)16-26
Number of pages11
JournalEuropean Journal of Operational Research
Volume247
Issue number1
DOIs
StatePublished - 16 Nov 2015

Keywords

  • Branch-and-cut algorithm
  • Critical elements detection
  • Minimum weighted dominating set
  • NP-hardness
  • Network interdiction

Fingerprint

Dive into the research topics of 'Minimum edge blocker dominating set problem'. Together they form a unique fingerprint.

Cite this