Minimum Degree Spanning Tree (1+ε,1)-Approximation in Near-Linear Time

Jul 16, 2026

Minimum Degree Spanning Tree (MDST) is a classic NP-hard problem where the goal is to minimize the maximum vertex degree in a spanning tree. While near-optimal additive guarantees were known since the early 1990s, obtaining comparably strong degree bounds in near-linear time remained open for decades. This work presents a first near-linear-time algorithm computing a spanning tree with maximum degree ⌈(1+ε)Δ*⌉+1 in O(m/ε^2) time, improving prior near-linear constructions. It also yields an O(mn^{2/3}) bound for degree Δ*+1, advancing the state of the art.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages65

Reading Time2 h 44 min

Introduction

Extended Abstract

Notations and Preliminaries

Our Framework

Basic Building Blocks

Our Algorithmic Template

A Key Subroutine: Applying an Effective Edge

High-Level Description of Our Algorithm

Searching for Augmenting Chains

Find-Chain Subroutine (Description)

Backward-Search

Correctness of Find-Chain

Analysis

Potential Function and Running Time Analysis

Full Version (Main Sections)

arXiv :2607 . 1 14 13v 1 [ cs .DS] 13 Jul 2026 Minimum Degree Spanning Tree: (1 + ε,1)-Approximation in Near-Linear Time Sayan Bhattacharya∗ Ermiya Farokhnejad† Thatchaphol Saranurak‡ Haoze Wang§ Abstract The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approxim˜ation guarantee was established since the early 1990s: F¨urer and Raghavachari [FR92] gave an O (mn)-time algorithm that computes a spanning tree with maximum degree ∆⋆ + 1, where ∆⋆ 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-lin˜ ear-time algorithm that computes a spanning tree with maximum degree ⌈(1 + ε)∆⋆⌉ + 1 in O(m/ε2 ) time. Prior near-linear-time algorithms either achieved the weaker bound ⌈(1 + ε)∆⋆⌉ + O(log n/ε2 ) [DHZ20] or required dense graphs with m ≥ n7/4 [CQT21, BFW26] . Using the same fram˜ework, our algorithm can also compute a sp˜ anning tree with maxi mum degree ∆⋆ + 1 in O (mn2/3) time, improving upon the recent O (mn3/4)-time algorithm of [BFW26] . These two results strictly improve all previous construction algorithms for the minimum degree spanning tree problem. ∗ University of Warwick, UK. †University of Warwick, UK. ‡University of Michigan, [USA.](USA. thsa@umich.edu. Supported)[ thsa@umich.edu](USA. thsa@umich.edu. Supported)[. Supported](USA. thsa@umich.edu. Supported) by NSF Grant CCF-2238138 and a Sloan Fellowship. § Peking University, China. Contents 1 Introduction 1 I Extended Abstract 3 2 Notations and Preliminaries 3 3 Our Framework 4 4 Basic Building Blocks 4 5 Our Algorithmic Template 7 5.1 A Key Subroutine: Applying an Effective Edge ..................... 7 5.2 High-Level Description of Our Algorithm ........................ 9 6 Searching for Augmenting Chains 10 6.1 Description of the Subroutine Find-Chain (h,(u, v)) .................. 10 6.2 Backward-Search ...................................... 10 6.3 Correctness of the Find-Chain Subroutine ........................ 11 7 Analysis 12 7.1 A Potential Function: Tail Independent Stable t-Chains ................ 13 7.2 Geometric Expansion of the Potential: Proving Property 2 of Lemma 7.7 ...... 14 7.3 Running Time Analysis .................................. 17 II Full Version 18 8 Introduction 18 8.1 Basic Notations ....................................... 18 8.2 The Main Subroutines ................................... 19 8.3 Concluding Main Results ................................. 19 9 Building Blocks 19 9.1 Reducible vs Non-Reducible Nodes ............................ 20 9.2 Configuration and Related Objects ............................ 20 9.3 Augmenting Chains as Black Box ............................. 21 10 Overview of Our Algorithm for Lemma 8.1 22 10.1 Applying Effective Edges ................................. 22 10.2 Description of the Algorithm for Lemma 8.1 ....................... 23 11 Augmenting Chains 24 11.1 Augmenting Chain and Its Application .......................... 24 11.2 Applying an Augmenting Chain to a Configuration ................... 25 12 Find-Chain Subroutine 27 12.1 Description of Find-Chain ................................. 27 12.2 Backward-Search ...................................... 28 12.3 Correctness of Find-Chain ................................. 30 13 Analysis 31 13.1 Correctness ......................................... 31 13.2 Number of Components of the Final Forest ....................... 31 13.3 Proof of Lemma 13.7: Part (i) ............................... 33 13.4 Proof of Lemma 13.7: Part (ii) .............................. 33 13.5 Deferred Proofs ....................................... 39 14 Running Time Analysis: Implementation Details 46 14.1 Main Data Structures ................................... 46 14.2 Implementing Round t ................................... 47 14

FAQs

What problem does the paper address?

The paper studies the Minimum Degree Spanning Tree (MDST) problem, which seeks a spanning tree minimizing the maximum degree among all vertices in an undirected connected graph.

What near-linear approximation guarantee is achieved?

It provides a near-linear-time algorithm that outputs a spanning tree whose maximum degree is ⌈(1+ε)Δ*⌉+1 with runtime O(m/ε^2), where Δ* is the optimal maximum degree.

How does the algorithm further improve results beyond the main approximation bound?

Using the same framework, it also constructs a spanning tree with maximum degree Δ*+1 in O(mn^{2/3}) time, improving upon a prior O(mn^{3/4})-time algorithm.

Jul 16, 2026

Upload by Genevieve