An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets Academic Article uri icon


  • © 2015 INFORMS. This paper considers the minimum k-connected d-dominating set problem, which is a fault-tolerant generalization of the minimum connected dominating set (MCDS) problem. Three integer programming formulations based on vertex cuts are proposed (depending on whether d < k, d D k, or d > k) and their integer hulls are studied. The separation problem for the vertex-cut inequalities is a weighted vertex-connectivity problem and is polytime solvable, meaning that the LP relaxation can be solved in polytime despite having exponentially many constraints. A new class of valid inequalities-r-robust vertex-cut inequalities-is introduced and is shown to induce exponentially many facets. Finally, a lazy-constraint approach is shown to compare favorably with existing approaches for the MCDS problem (the case k D d D 1), and is in fact the fastest in literature for standard test instances. A key subroutine is an algorithm for finding an inclusion-wise minimal vertex cut in linear time. Computational results for 4k1 d5D421 151 421 251 431 351 441 45 are provided as well.

altmetric score

  • 0.5

author list (cited authors)

  • Buchanan, A., Sung, J. S., Butenko, S., & Pasiliao, E. L.

citation count

  • 17

publication date

  • February 2015