The Probabilistic Minimum Spanning Tree Problem: Complexity and Combinatorial Properties

Excerpt from The Probabilistic Minimum Spanning Tree Problem

In this paper we consider a natural probabilistic variation of this classical problem. In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. Formally, given a weighted graph G (v, E) and a probability of presence p(s) for each subset S of V, we want to construct an a priori spanning tree of minimum expected length in the following on any given instance of the problem delete the vertices and their adjacent edges among the set of absent vertices provided that the tree remains connected. The problem of finding an a priori spanning tree of minimum expected length is the probabilistic minimum spanning tree (pmst) problem. In order to clarify the definition of the pmst problem, consider the example in Figure 1. If the a priori tree is T and nodes are the only ones not present, the tree becomes ti. One can easily observe that if every node is present with probability p. 1 for all i E V then the problem reduces to the classical mst problem.