Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier

Abstract

We consider the ``minimum degree spanning tree'' problem. As input, we receive an undirected, connected graph $G=(V,E)$ with $n$ nodes and $m$ edges, and our task is to find a spanning tree $T$ of $G$ that minimizes ${\max }_{u\in V}{\text{deg}}_T(u)$, where ${\text{deg}}_T(u)$ denotes the degree of $u\in V$ in $T$. The problem is known to be NP-hard. In the early 1990s, an influential work by Fürer and Raghavachari presented a local search algorithm that runs in $\tilde{O}(mn)$ time, and returns a spanning tree with maximum degree at most $\hat{I}{”}^{\star }+1$, where $\hat{I}{”}^{\star }$ is the optimal objective. This remained the state-of-the-art runtime bound for computing an additive one approximation, until now. We break this $O(mn)$ runtime barrier dating back to three decades, by providing a deterministic algorithm that returns an additive one approximate optimal spanning tree in $\tilde{O}(m{n}^{3/4})$ time. This constitutes a substantive progress towards answering an open question that has been repeatedly posed in the literature [Pettie'2016, Duan and Pettie'2020, Saranurak'2024]. Our algorithm is based on a novel application of the blocking flow paradigm.

Accepted at STOC 2026