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

arXiv:2602.23448v1 Announce Type: new
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”{u}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 $Delta^star+1$, where $Delta^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}(mn^{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.