Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

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(n2) 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 γ ≥ 1 is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal Omega(n2)-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.