An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices

Given a graph $$G=(V,E)$$ G = ( V , E ) , the minimum branch vertices problem consists in finding a spanning tree $$T=(V,E')$$ T = ( V , E ′ ) of G minimizing the number of vertices with degree greater than two. We consider a simple combinatorial lower bound for the problem, from which we propose a decomposition approach. The motivation is to break down the problem into several smaller subproblems which are more tractable computationally, and then recombine the obtained solutions to generate a solution to the original problem. We also propose effective constructive heuristics to the problem which take into consideration the problem’s structure in order to obtain good feasible solutions. Computational results show that our decomposition approach is very fast and can drastically reduce the size of the subproblems to be solved. This allows a branch and cut algorithm to perform much better than when used over the full original problem. The results also show that the proposed constructive heuristics are highly efficient and generate very good quality solutions, outperforming other heuristics available in the literature in several situations.