A rigorous analysis of the cavity equations for the minimum spanning tree

Abstract

We analyze a new general representation for the Minimum Weight Steiner Tree (MST) problem which translates the topological connectivity constraint into a set of local conditions which can be analyzed by the so called cavity equations 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.

5 pages, 1 figure

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Learning by message-passing in networks of discrete synapses
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Statistical Mechanics of Steiner trees
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs

Cited by in corpus (11)

• Finding undetected protein associations in cell signaling by belief propagation
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Networking - A Statistical Physics Perspective
• The zero-patient problem with noisy observations
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• The edge-disjoint path problem on random graphs by message-passing
• Clustering with shallow trees
• The cavity approach for Steiner trees packing problems
• Practical optimization of Steiner Trees via the cavity method
• A cavity approach to optimization and inverse dynamical problems
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching