Minimum Degree Spanning Tree: $(1+\hat{I}\mu ,1)$-Approximation in Near-Linear Time

Abstract

The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gave an $\tilde{O}(mn)$-time algorithm that computes a spanning tree with maximum degree $\hat{I}{”}^{\star }+1$, where $\hat{I}{”}^{\star }$ denotes the optimum value. Whether similarly strong guarantees can be achieved in near-linear time has remained open for over three decades. We give the first near-linear-time algorithm that computes a spanning tree with maximum degree $\lceil (1+\hat{I}\mu )\hat{I}{”}^{\star }\rceil +1$ in $\tilde{O}(m/\hat{I}{\mu }^2)$ time. Prior near-linear-time algorithms either achieved the weaker bound $\lceil (1+\hat{I}\mu )\hat{I}{”}^{\star }\rceil +O(\log n/\hat{I}{\mu }^2)$ [DHZ20] or required dense graphs with $m\ge n^{7/4}$ [CQT21,BFW26]. Using the same framework, our algorithm can also compute a spanning tree with maximum degree $\hat{I}{”}^{\star }+1$ in $\tilde{O}(m{n}^{2/3})$ time, improving upon the recent $\tilde{O}(m{n}^{3/4})$-time algorithm of [BFW26]. These two results strictly improve all previous construction algorithms for the minimum degree spanning tree problem.

Topics & keywords