The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence Extended Abstract

Abstract

We study the problem of detecting and recovering a planted spanning tree M_n^* hidden within a complete, randomly weighted graph G_n. Specifically, each edge e has a non-negative weight drawn independently from P_n if e ∈ M_n^* and from Q_n otherwise, where P_n ≡ P is fixed and Q_n scales with n such that its density at the origin satisfies lim_n→∞ n Q’_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.