Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Nate Veldt; Thomas Stanley; Benjamin W. Priest; Trevor Steil; Keita Iwabuchi; T. S. Jayram; Grace J. Li; Geoffrey Sanders

cs.DSFeb 27, 2026

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Authors: Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil, Keita Iwabuchi, T. S. Jayram, Grace J. Li, Geoffrey Sanders

Organizations: Texas A&M University · Lawrence Livermore National Laboratory

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.

Figures & tables

Panel of Figure 1 — Figure 1: (a) The forest obtained by terminating Kruskal’s algorithm early for a set of 100 points. (b) Running Kruskal’s algorithm to the end leads to a full MST. (c) The initial forest can be viewed as a heuristic prediction for the forest in (a). For this example, $\gamma(\mathcal{P})\approx 1.06$ . (d) Solving metric forest completion problem produces a full spanning tree that approximates the true MST.

Figure 2: The MFC instance from Theorem 3 when

\ell=3

and

p=5

. Initial forest edges are black solid lines; these define

p

components with

\ell+1

points each. Points with black centers are representatives. Two points have distance

\varepsilon

if they are in the same gray enclosing region, otherwise they have distance 1. These distances can be realized by associating each point with a vector of length

p+\max\{\ell,p\}

and using

\ell_{\infty}

distance. The optimal spanning tree is achieved by adding the red dashed edges, which all have weight

\varepsilon

. MultiRepMFC only adds edges incident to representatives, and therefore completes the forest with

\ell-1

edges of weight 1 (e.g., dotted blue edges).

Panel of Figure 3 — Figure 3: We display the performance of each variant of MultiRepMFC as runtime increases. Each point corresponds to running one method with a fixed budget $b$ . The top row shows the value of $\varepsilon$ such that a method obtains a $(1+\varepsilon)$ -approximation in practice. The second row shows the value $\varepsilon_{\alpha}$ such that we can guarantee a $(1+\varepsilon_{\alpha})$ -approximation using Theorem 1 . Computing $\varepsilon_{\alpha}$ is fast. Computing $\varepsilon$ is impractical as it requires optimally solving MFC. The last row shows the gap between $\alpha$ and the true approximation as runtime increases. We see that all variants of MultiRepMFC provide a useful interpolation between the existing MFC-Approx algorithm ( $b=0$ vertical dashed line) and an optimal MFC algorithm (right vertical dashed line). All plots also show that dynamic programming produces better true approximations (top row), much better approximation bounds (middle row), and is faster at shrinking the gap between the bound and true approximation (last row). For Cooking , 16 random orderings of the entire dataset ( $n=39,774$ ) were used, for all others we take 16 uniform random samples of size $n=30,000$ . Average results are then displayed.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: We display the performance of each variant of MultiRepMFC as budget increases. Each point corresponds to running one method with a fixed budget $b$ .

Panel of Figure 5 — Figure 5: For each dataset, we display the completion ratio : the weight of new edges added by MultiRepMFC , divided by the weight of the new edges added by an optimal solution for MFC. Adding a small number of extra representatives leads to an even more dramatic improvement to the completion ratio than to the MFC Cost ratio .

Learning-Augmented Algorithms

Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.

See all 54 papers

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
Sep 8, 2026Meher Chaitanya, Cameron Musco, Aristides GionisGraph Sparsification Matrix Factorization
KTH Royal Institute of Technology Stockholm, Sweden · University of Massachusetts Amherst Amherst, Massachusetts, USA
Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem
Apr 22, 2026Bo-Cheng Lin, Yi Mei, Mengjie ZhangTraveling Salesperson Problem Graph Sparsification
Centre for Data Science and Artificial Intelligence, and the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, 6140, New Zealand
A new classification method based on Minimum Spanning Trees
Jun 19, 2026Julio González-Díaz, Beatriz Pateiro-López, Iria Rodríguez-AcevedoClassification
Department of Statistics, Mathematical Analysis and Optimization and MODESTYA Research Group, University of Santiago de Compostela, Santiago de Compostela, 15782, Galicia, Spain · CITMAga (Galician Center for Mathematical Research and Technology), University of Santiago de Compostela, Santiago de Compostela, 15782, Galicia, Spain

Sep 8, 2026J/K move · Enter open · S save

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

Meher Chaitanya, Cameron Musco, Aristides Gionis

KTH Royal Institute of Technology Stockholm, Sweden · University of Massachusetts Amherst Amherst, Massachusetts, USA

Graph Sparsification Matrix Factorization

Open paper AskPDF arXiv

Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the factor, whose construction cost is amortized across these solves. But eliminating a vertex, the pivot, creates a dense Schur-complement clique among its

d

active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-

ρ

, which replaces each pivot neighbor with

ρ

copies, each carrying a

1/ρ

share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in

O(ρd)

time, and satisfies a

1/ρ

bound on the second moment of the normalized local Schur error. Increasing

ρ

therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.

Abstract

Learning-Augmented Algorithms

Explore similar work

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem

A new classification method based on Minimum Spanning Trees