{"ID":6537560,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11413","arxiv_id":"2607.11413","title":"Minimum Degree Spanning Tree: $(1+ε,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 $Δ^\\star+1$, where $Δ^\\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+ε)Δ^\\star\\rceil+1$ in $\\tilde O(m/ε^2)$ time. Prior near-linear-time algorithms either achieved the weaker bound $\\lceil (1+ε)Δ^\\star\\rceil + O(\\log n/ε^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 $Δ^\\star+1$ in $\\tilde O(mn^{2/3})$ time, improving upon the recent $\\tilde O(mn^{3/4})$-time algorithm of [BFW26]. These two results strictly improve all previous construction algorithms for the minimum degree spanning tree problem.","short_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 $Δ^\\star+1$, where $Δ^\\star$ denotes the optimum value....","url_abs":"https://arxiv.org/abs/2607.11413","url_pdf":"https://arxiv.org/pdf/2607.11413v1","authors":"[\"Sayan Bhattacharya\",\"Ermiya Farokhnejad\",\"Thatchaphol Saranurak\",\"Haoze Wang\"]","published":"2026-07-13T11:22:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}