The Probabilistic Minimum Spanning Tree Problem - Complexity and Combinatorial Properties #270734

In this paper we consider a natural probabilistic variation of the classical minimum spanning tree (MST) problem, which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed form expression for the expected length of a given spanning tree. Based on these expressions we prove that the problem is N P - complete. We further examine some combinatorial properties of the problem, establish the relation of the PMST problem with the MST problem and the network design problem and examine some cases where the problem is solvable in polynomial time.