An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
Austin Buchanan, Je Sang Sung, Sergiy Butenko, Eduardo L. Pasiliao
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 1
Abstract
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 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 = 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.
Keywords
connected dominating set, k-connected m-dominating set, integer programming, fault-tolerant
Enable JavaScript for citation tools and additional paper interactions.