TY - JOUR
T1 - Minimum edge blocker dominating set problem
AU - Mahdavi Pajouh, Foad
AU - Walteros, Jose L.
AU - Boginski, Vladimir
AU - Pasiliao, Eduardo L.
N1 - Publisher Copyright:
© 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) withinthe International Federation of Operational Research Societies (IFORS). All rightsreserved.
PY - 2015/11/16
Y1 - 2015/11/16
N2 - 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.
AB - 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.
KW - Branch-and-cut algorithm
KW - Critical elements detection
KW - Minimum weighted dominating set
KW - NP-hardness
KW - Network interdiction
UR - http://www.scopus.com/inward/record.url?scp=84937514675&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937514675&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2015.05.037
DO - 10.1016/j.ejor.2015.05.037
M3 - Article
AN - SCOPUS:84937514675
SN - 0377-2217
VL - 247
SP - 16
EP - 26
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -