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

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∈V deg T (u), where deg T (u) denotes the degree of u ∈ 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 Õ(mn) time, and returns a spanning tree with maximum degree at most ∆ ⋆ + 1, where ∆ ⋆ 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 Õ(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.