This paper introduces a novel cycle basis-driven algorithm for computing tight lower and upper bounds on four fundamental degree-dependent spanning tree problems: the Minimum Branch Vertices Spanning Tree Problem (MBV), the Minimum Leaves Spanning Tree Problem (ML), the Maximum Internal Spanning Tree Problem (MIN), and the Minimum Degree Sum of Branch Vertices in any Spanning Tree Problem (MDSBV). These problems are critical for optimizing network design, particularly in optical networks and infrastructure resilience, where minimizing hardware costs and maximizing efficiency are paramount. Our unified framework leverages cycle basis decomposition to derive rigorous bounds with polynomial-time complexity, offering a significant improvement over existing Integer Linear Programming (ILP) relaxations and metaheuristic approaches. The method adapts seamlessly to all four problems with minimal modifications, ensuring versatility and scalability. Experimental results on standard benchmarks demonstrate that our approach achieves near-optimal solutions with substantially reduced computational overhead compared to exact methods, while outperforming heuristic baselines in solution quality.
Merabet et al. (Mon,) studied this question.