Geometric properties of minimal-cost spanning trees*

The minimal-cost spanning tree (MST) problem is one of the oldest combinatorial optimization problems of computer science: given a graph with a unique cost associated with each edge, the MST is the subset of edges that will connect all vertices of the graph to each other at lowest total cost. While the MST is easy to compute (i.e., of polynomial complexity), it is of interest both intrinsically and as a heuristic approximation to harder questions in optimization, such as the Steiner tree and Traveling Salesman problems. Using techniques of statistical field theory, we study the random MST where the edge costs are independent, identically distributed, random variables. We develop a mean field theory by solving the MST exactly on the Bethe lattice using the relationship between bond percolation and Kruskal's greedy algorithm for the MST. These considerations carry over to finite dimensional lattices and the field theory for percolation in $6- \epsilon$ dimensions. From this we find that the critical dimension $d_c = 6$ for the MST problem, contrary to the result $d_c = 8$ previously suggested by Newman and Stein. Finally we calculate to order $\epsilon$ the Hausdorff (fractal) dimension of the unique path on the MST connecting two widely separated points.