A Hybrid Branch-and-cut Algorithm for the Minimum Outer-connected Dominating Set Problem

In this paper, we propose Branch-and-cut algorithms for the Minimum Outer
Connected Dominating Set Problem. We first present two integer programming formulati-
ons. The first uses directed cutset inequalities to enforce external connectivity, while the
second is based on the classical Miller–Tucker–Zemlin (MTZ) inequalities. Besides exact al-
gorithms derived from these formulations, we introduce a hybrid Branch-and-cut algorithm
with two combined phases. In the first phase, the linear relaxation of the cutset formula-
tion is solved in order to identify a strong set of valid inequalities. In the second phase,
these inequalities are used to strengthen an MTZ-based branch-and-cut algorithm. The
hybrid approach separates cutset inequalities only at the root node and uses MTZ inequa-
lities at the remaining nodes. Computational experiments show that the hybrid algorithm
outperforms the two other proposed algorithms for all metrics considered here.