The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm

Given an edge weighted undirected graph GG and a positive integer dd, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of GG, such that each vertex is either a leaf or else has degree at least dd in the tree. In this paper, we discuss two formulations for MDMST based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming (LP) bounds with other bounds in the literature. Aiming to overcome the fact that the strongest of the two models, the directed one, is not symmetric with respect to the LP bounds, we also presented a symmetric compact reformulation, devised with the application of an Intersection Reformulation Technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds is very time consuming. Thus, better computational results were obtained by a Branch-and-cut algorithm based on the original directed formulation. With the proposed method, several new optimality certificates and new best upper bounds for MDMST were provided.

► We provide several formulations for the problem.
► Formulations are compared in terms of their LP relaxation strength.
► Lower bounds implied by the strongest model are expensive to compute.
► The best algorithm is based on a weaker formulation.
► Upper bounds obtained in this study improve previous results.