Problem 7 - Graphs

For a simple connected graph $G=(V,E)$ with vertex set $V$ and edge set $E$, each edge $e_i \in E$ disappears with probability $p_i$ independently. Give an algorithm to compute a spanning tree of the original graph $G$ such that all its edges survive with maximum probability. Describe its validity and computational complexity.

We shall consider the simple connected graph $G$ as a weighted graph where all the edges $e_i$ have a $p_i$ weight. We want to compute a spanning tree, i.e. a collection of edges connecting all the vertices. This tree will have the property of lowering the sum of the disparition probabilities $p_i$ so that the edges will survive with the maximum probability. The problem is then reduced to the calculation of a minimum spanning tree.

See [SED00] for a detailed answer.