A rigorous analysis of the cavity equations for the minimum spanning tree
Mohsen Bayati, Alfredo Braunstein, Riccardo Zecchina · Journal of Mathematical Physics · 2008
We analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the so-called cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.