# Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty

arXiv: https://arxiv.org/abs/2206.15201 · HTML: https://mlsanity.com/paper/2206.15201/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2022.

## Built on by (most cited first, 7 of 7)

- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)
- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Sorting and Hypergraph Orientation under Uncertainty with Predictions](https://mlsanity.com/paper/2305.09245/) (2023)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations](https://mlsanity.com/paper/2610.14996/) (2026)

## Abstract (arXiv)

We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral γ≥ 2, we present algorithms that are γ-robust and (1+frac1γ)-consistent, meaning that they use at most γ OPT queries if the predictions are arbitrarily wrong and at most (1+frac1γ)OPT queries if the predictions are correct, where OPT is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of~2, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets -- the key to lower-bounding the optimum -- by proposing novel global witness set structures and completely new ways of adaptively using those.