Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Nate Veldt, Thomas Stanley, Benjamin Priest, Trevor Steil, Keita Iwabuchi, T.S. Jayram, Grace Li, Geoff Sanders

International Conference on Learning Representations 2026 (ICLR 2026) Conference

We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes $\Omega(n^2)$ time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a $(2\gamma + 1)$-approximation for the original MST problem, where $\gamma \geq 1$ is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal $\Omega(n^2)$-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen "representative" points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and $(2\gamma+1)$ for metric MST to 2 and $2\gamma$ respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.