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


  • 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 = 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 inequalitiesr-robust vertex-cut inequalitiesis 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 = 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 (k, d) = (2,1), (2,2), (3,3), (4,4) are provided as well.

published proceedings

  • INFORMS Journal on Computing

altmetric score

  • 0.5

author list (cited authors)

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

citation count

  • 23

publication date

  • January 2015