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

Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang · 2026

Read Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O ⁡ ( m ​ n ) O(mn) Time Barrier by Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23448.txt.

Description

Sayan Bhattacharya and two co-authors improve the classic minimum-degree spanning tree problem: given a connected graph, find a spanning tree whose largest node degree is as small as possible. The problem is NP-hard. Since the early 1990s, the best method added at most one to the optimal degree but ran in roughly O(mn) time.

The authors break that three-decade runtime barrier. Their deterministic algorithm still adds at most one to the optimal degree but runs in roughly O(mn to the three-quarters) time. Their method rests on a novel use of the blocking flow paradigm. The result is substantive progress toward a long-standing open question, posed repeatedly in the literature, on whether the old runtime bound could be beaten.

Catalog record

CREATORSayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE152 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23448

Browse the full library · About the Tower of Babel