The Planted Spanning Tree Problem

Mehrdad Moharrami, Cristopher Moore, Jiaming Xu

We study the problem of detecting and recovering a planted spanning tree $M_n^{\ast }$ hidden within a complete, randomly weighted graph $G_n$. Specifically, each edge $e$ has a non-nega…