Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
2026-02-27 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors improved computer methods for quickly connecting points with lines so that all points are linked with nearly the shortest total length possible, a problem called the minimum spanning tree (MST). They build on a previous approach where a partially connected set of points (a forest) is completed into a full tree. Their new method smartly picks certain key points to reduce the number of connections that need checking, leading to better approximations than before while still being faster than fully optimal methods. They show their improvements are the best possible for the hardest cases and back up their theory with practical experiments.
minimum spanning treemetric spaceapproximation algorithmforest completionsubquadratic complexityrepresentative pointsapproximation factoralgorithm analysisexperimental evaluationcomputational geometry
Authors
Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil, Keita Iwabuchi, T. S. Jayram, Grace J. Li, Geoffrey Sanders
Abstract
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 $Ω(n^2)$ time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a $(2γ+ 1)$-approximation for the original MST problem, where $γ\geq 1$ is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal $Ω(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γ+1)$ for metric MST to 2 and $2γ$ 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.