Random spanning trees on homogeneous graphs

Abstract

Spanning trees have been studied as combinatorial objects for a long time. However, they have found great use in other disciplines recently. Disjoint spanning trees are important in fault-tolerant broadcasting or load-balancing communication systems in interconnection networks. For instance, providing completely independent spanning trees (pairwise edge-disjoint and internally disjoint spanning trees) guarantees uninterrupted service. Completely independent spanning trees were introduced by T. Hasunuma and then have been studied on different classes of graphs. The problem to determine whether there exist two completely independent spanning trees in a graph G is NP-hard . In this context, one may aim to construct spanning trees that collide as little as possible. This problem has been studied by Albin, Poggi-Corradini, et al.. Here we think of spanning trees of a graph as random variables and we aim to find a probability mass function (pmf) that minimizes the expected overlap of two random spanning trees.

We study the minimum expected overlap problem for a special class of graphs. We provide a necessary and sufficient condition for a homogeneous graph to admit optimal weights. Given an unweighted graph $G$, this entails obtaining a weighted graph on the same vertex-set so that the weighted uniform spanning tree pmf is optimal for the minimum expected overlap problem. We use the maximum entropy problem to show this result and apply gradient descent method for the dual objective function to find the optimal weights.

In addition, we show that the objective function of the minimum expected overlap problem is quasiconvex in each coordinate. Essentially, we show that there is a unique minimizer which allows us to introduce convergent algorithms to compute the optimal weights.