Preprint
The Planted Spanning Tree Problem
ArXiV.org
Cornell University
02/12/2025
DOI: 10.48550/arxiv.2502.08790
Abstract
We study the problem of detecting and recovering a planted spanning tree M∗n hidden within a complete, randomly weighted graph Gn. Specifically, each edge e has a non-negative weight drawn independently from Pn if e∈M∗n and from Qn otherwise, where Pn≡P is fixed and Qn scales with n such that its density at the origin satisfies limn→∞nQ′n(0)=1. We consider two representative cases: when M∗n is either a uniform spanning tree or a uniform Hamiltonian path. We analyze the recovery performance of the minimum spanning tree (MST) algorithm and derive a fixed-point equation that characterizes the asymptotic fraction of edges in M∗n successfully recovered by the MST as n→∞. Furthermore, we establish the asymptotic mean weight of the MST, extending Frieze's ζ(3) result to the planted model. Leveraging this result, we design an efficient test based on the MST weight and show that it can distinguish the planted model from the unplanted model with vanishing testing error as n→∞. Our analysis relies on an asymptotic characterization of the local structure of the planted model, employing the framework of local weak convergence.
Details
- Title: Subtitle
- The Planted Spanning Tree Problem
- Creators
- Mehrdad Moharrami - University of IowaCristopher Moore - Santa Fe InstituteJiaming Xu - Duke University
- Resource Type
- Preprint
- Publication Details
- ArXiV.org
- Publisher
- Cornell University; Ithaca, New York
- DOI
- 10.48550/arxiv.2502.08790
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 02/12/2025
- Academic Unit
- Computer Science
- Record Identifier
- 9984791071402771
Metrics
3 Record Views